wake-up-neo.net

Erläuterung der Laufzeiten von BFS und DFS

Warum sind die Laufzeiten von BFS und DFS O (V + E), insbesondere wenn es einen Knoten gibt, der eine gerichtete Kante zu einem Knoten hat, der vom Scheitelpunkt aus erreicht werden kann, wie in diesem Beispiel auf der folgenden Site

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

36
miss24

E ist die Menge aller Kanten im Graphen, als G = {V, E}. Also, | E | ist die Anzahl aller Kanten im Diagramm.

Dies allein sollte ausreichen, um Sie davon zu überzeugen, dass die Gesamtkomplexität nicht | V | sein kann mal | E |, da wir nicht für jeden Scheitelpunkt über alle Kanten im Graphen iterieren.

In der Darstellung der Adjazenzliste durchlaufen wir für jeden Knoten v nur die Knoten, die ihm benachbart sind.

Die | V | Faktor der | V | + | E | scheint von der Anzahl der ausgeführten Warteschlangenoperationen zu stammen.

Beachten Sie, dass die Komplexität des Algorithmus von der verwendeten Datenstruktur abhängt. effektiv besuchen wir jede Information, die in der Darstellung des Graphen vorhanden ist, weshalb für die Matrixdarstellung des Graphen die Komplexität V Quadrat wird.

Zitat aus Cormen,

Die Operationen des Einreihens und Ausreihens dauern O(1) Zeit, so dass die Gesamtzeit, die für Warteschlangenoperationen aufgewendet wird, O (V) ist. Weil die Adjazenzliste jedes Scheitelpunkts nur gescannt wird, wenn der Scheitelpunkt ist In der Warteschlange wird jede Adjazenzliste höchstens einmal gescannt. Da die Summe der Längen aller Adjazenzlisten Θ (E) ist, beträgt die Gesamtzeit für das Scannen der Adjazenzlisten O (E). Der Aufwand für die Initialisierung beträgt O ( V) und somit ist die Gesamtlaufzeit von BFS O (V + E). "

40

Diese Ausgabe dauert ungefähr 4 Stunden, aber ich glaube, ich habe eine einfache Möglichkeit, mir ein Bild zu machen. Am Anfang war ich versucht, O (V * E) zu sagen.

Fassen Sie den Algorithmus, den Sie in Cormen finden, folgendermaßen zusammen: http: //www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm Sie haben etwas so was :

für (vi in ​​V) Einige O(1) Anweisungen für (e in Adj (vi)) {Einige O(1) Anweisungen}

Die Frage ist, wie viele Anweisungen hier ausgeführt werden? das wird die Sigma-Summe (Adj (vi)) sein, und dieser Wert wird durch 2 | E |.

Zu Beginn denken wir automatisch darüber nach, die Anzahl der Iterationen der inneren und äußeren Schleife zu multiplizieren. In diesem Fall ist die Gesamtzahl der Iterationen der inneren Schleife jedoch eine Funktion des äußeren Iterators, sodass keine Multiplikation möglich ist.

18
Jose Francisco

Sie besuchen jeden Edge höchstens zweimal. Es gibt E-Kanten. Es wird also 2 * E Edge-Besuchsoperationen geben. Plus die Knoten, die keine Kanten oder mit anderen Worten mit Grad 0 haben. Es können höchstens V solche Knoten sein. Die Komplexität ist also: O (2 * E + V) = O (E + V)

8
Fallen

Dies wird deutlich, wenn Sie ein Diagramm als Datenstruktur sehen, die als benachbarte Liste dargestellt wird

enter image description here

Sie sehen Scheitelpunkte: A, B, C, D, E und benachbarte Scheitelpunkte für jeden Scheitelpunkt/Knoten als Liste aus diesen Scheitelpunkten. Sie müssen alle Kästchen "sehen", um zu überprüfen, ob sie im Falle eines zyklischen Graphen "besucht" wurden, oder Sie gehen einfach alle Kinder durch, wenn es sich um einen baumartigen Graphen handelt

0
AleC

Sie iterieren über das | V | Knoten, für höchstens | V | mal. Da wir eine Obergrenze von | E | haben Insgesamt werden die Kanten in der Grafik höchstens mit | E | markiert Kanten. Unterschiedliche Eckpunkte haben eine unterschiedliche Anzahl benachbarter Knoten, so dass wir nicht einfach | V | * | E | multiplizieren können (dies bedeutet, dass wir für jeden Scheitelpunkt | E | Kanten durchlaufen, was nicht wahr ist. | E | ist die Gesamtzahl der Kanten über alle Knoten.) Stattdessen überprüfen wir V Knoten und insgesamt E Kanten. Am Ende haben wir O (| V | + | E |)

Für DFS ist es etwas Ähnliches. Wir durchlaufen alle Adjazenzlisten eines Vertices und rufen DFS (v) auf, wenn es nicht besucht wurde, was bedeutet, dass | V | auftritt Zeitschritte plus der Zeit, die erforderlich ist, um benachbarte Knoten zu besuchen (im Wesentlichen bilden diese eine Kante, und wir haben insgesamt | E | Kanten, daher O (V + E) Zeit.

    private static void visitUsingDFS(Node startNode) {
        if(startNode.visited){
            return;
        }
        startNode.visited = true;
        System.out.println("Visited "+startNode.data);
        for(Node node: startNode.AdjacentNodes){
            if(!node.visited){
                visitUsingDFS(node);
            }
        }
    }
0
Bavinho