Nachbarschaft-Liste Darstellung eines gerichteten Graphen

Gegeben, eine Nachbarschaft-Liste Darstellung eines gerichteten Graphen, wie lange dauert es
zur Berechnung der aus-Grad von jedem Eckpunkt? Wie lange dauert es, um zu berechnen,
in-Grad?

Dank

InformationsquelleAutor user2558869 | 2013-08-06
  1. 4

    Beide sind O(m + n) wo m ist die Anzahl der Kanten und n ist die Anzahl der vertices.

    Starten eine Reihe von Leistungsindikatoren, eine für jeden Scheitelpunkt, eine für in-degree und out für out-degree.

    Scannen der Kanten. Für die aus Knoten, jede Kante, hinzufügen, um das aus-Maß Zähler für den jeweiligen Eckpunkt. Für die Knoten jeder Kante, hinzufügen der in-Grad-Zähler für diesen vertex. Dies ist O(m) Betrieb.

    Ausgabe der out-degree und degree-Zähler für jeden vertex, die O(n).

    So kommen Sie O(m + n).

    • ja ich habe gesehen, dass online-vor...wäre es die gleiche wie weit wie O(V+E)...oder wäre es O(E+V)
    • Es ist genau das gleiche.
    • Korrekt ist O(V+E) oder O(E+V)
    • Sorry V steht für vertex und E für Kanten
    • Spielt es eine Rolle, wenn Sie Sie mit der ()
    • Auch, es ist nur ein O oder ist das O mit einem Strich in der Mitte?
    • Betrachten Sie die definition: en.wikipedia.org/wiki/Big_O_notation#Formal_definition. Wenn Sie nicht vertraut sind mit der notation und es kann nicht herausfinden, trotz Ihrer besten Bemühungen, fühlen Sie sich frei den posten notational Fragen in einem separaten math.stackexchange post

    InformationsquelleAutor jason
  2. 5

    Nachbarschaft-Liste Darstellung eines gerichteten Graphen:

    Out-Grad jedes Knotens

    1. Graphen aus-Grad eines Knotens u ist gleich der Länge von Adj[u].

    2. Die Summe der Längen aller Nähe-Listen in Adj ist |E|.

    3. Damit die Zeit zu berechnen die aus-Grad jeder vertex ist Θ(V + E)

    In-Grad jedes Knotens

    1. Der in-Grad eines Knotens u ist gleich der Anzahl der Male es wird in alle Listen im Adj.

    2. Wenn wir suchen, alle Listen für jeden vertex, die Zeit zu berechnen, die in Grad jedes Knotens ist Θ(VE)

    3. Alternativ können wir reservieren ein array T der Größe |V| und initialisieren Sie die Einträge zu null.

    4. Müssen wir nur Scannen Sie die Listen in Adj einmal, Inkrementierung von T[u] wenn wir sehen, wie 'u' in den Listen.

    5. Werte in T wird der in-Grad von jedem vertex.

    6. Diese kann getan werden, in Θ(V + E) Zeit mit Θ(V) zusätzlichen Stauraum.

    • Dies sollte sein die beste Antwort.
    InformationsquelleAutor Manu Thakur
  3. 1

    Da, sein ein gerichteter graph und nur die Nähe Liste gegeben ist.

    Sich die Zeit, die zum zählen der Anzahl der aus-Grad wäre theta (M+N), wobei M die Anzahl der Knoten und N bezieht sich auf Anzahl der Kanten.

    In der Erwägung, dass für die Zählung der Anzahl der in-Grad für alle Knoten, den Sie haben, um die Anzahl der vorkommen des Knotens in allen anderen(restlichen vertices) angrenzens Liste. Ja, es dauern würde, theta(MN).

    Jedoch, wenn Sie pflegen ein Array der Größe M, dann kannst du das zählen der in-Grad in theta(M+N) mit einem zusätzlichen Raum Speicher von theta(M)

    InformationsquelleAutor letsBeePolite
  4. 1

    out-degree für jeden vertex:theta(E)

    in-degree für jeden vertex:O(E)

    E ist die Anzahl der Kanten des Graphen

    InformationsquelleAutor user5099144
  5. -1

    Computing sowohl die in-degree und out-degree dauert theta(m + n) für einen Graphen mit m Knoten und n Kanten. Der Grund, dass es theta(m+n) und nicht O(m + n), weil, was immer die Grafik , es hat zu gehen durch jeden Eckpunkt m und jede Kante n.

    InformationsquelleAutor ssmetkar
  6. -2

    Gegeben, eine Nachbarschaft-Liste Darstellung von Adj, ein gerichteter graph, der Grad eines Knotens u ist gleich der Länge von Adj[u],
    und die Summe der Längen aller Nähe-Listen in Adj ist |E|. So ist die Zeit zu berechnen die aus-Grad eines jeden Knoten ist Θ(|V| + |E|).

    Der in-Grad eines Knotens u ist gleich der Anzahl der Male es wird in alle Listen in Adj., Wenn wir suchen, alle Listen für jeden
    vertex, die Zeit zu berechnen, die im Grad eines jeden Knoten ist Θ(|V|.|E|).

    (Alternativ können wir reservieren ein array T der Größe |V| und initialisieren Sie die Einträge zu null. Dann müssen wir nur Scannen Sie die Listen in
    Adj einmal, Inkrementierung von T[u] wenn wir sehen, u in den Listen. Die Werte in T wird der in-Grad von jedem vertex. Dies kann
    getan in Θ(|V| + |E|) Zeit mit Θ(|V|) zusätzlichen Speicher.)

    InformationsquelleAutor 1 0
Schreibe einen Kommentar