Breite der ersten Suche Komplexitätsanalyse der Zeit

Question

Die Zeitkomplexität, um über jede angrenzende Kante eines Scheitelpunktes zu gehen, ist O(N), wobei N die Anzahl der angrenzenden Kanten ist. Für die Anzahl der Vertices V wird die Zeitkomplexität O(V*N) = O(E), wobei E die Gesamtzahl der Kanten im Graphen ist. Da das Entfernen und Hinzufügen eines Scheitelpunkts von/zu der Warteschlange O(1) ist, warum wird es zur gesamten Zeitkomplexität von BFS als O(V+E) hinzugefügt.

Answer 1

Ich hoffe, dass dies für jeden hilfreich ist, der Probleme hat, die Komplexität der Rechenzeiten für Breathth First Search a.k.a BFS zu verstehen.

Queue graphTraversal.add(firstVertex); 

// This while loop will run V times, where V is total number of vertices in graph. 
while(graphTraversal.isEmpty == false) 

    currentVertex = graphTraversal.getVertex(); 

    // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex. 
    while(currentVertex.hasAdjacentVertices) 
     graphTraversal.add(adjacentVertex); 

    graphTraversal.remove(currentVertex); 

Zeitkomplexität ist wie folgt:

V * (O(1) + Eaj + O(1)) 
V + V * Eaj + V 
2V + E(total number of edges in graph) 
V + E 

Ich habe versucht, den Code und die Komplexität Berechnung zu vereinfachen, aber immer noch, wenn Sie irgendwelche Fragen haben, lassen Sie mich wissen.

Answer 2

Durchführen eines O(1) Betrieb L Zeiten, Ergebnisse zu O(L) Komplexität. Das Entfernen und Hinzufügen eines Scheitelpunkts aus/zur Warteschlange ist also O (1), aber wenn Sie dies für V Scheitelpunkte tun, erhalten Sie O(V) Komplexität. Daher

Answer 3

Betrachtet man die folgende Graphik, sehen wir, wie die Zeitkomplexität O (| V | + | E |), aber nicht O (V * E) ist.

Adjazenzliste

V  E 
v0:{v1,v2} 
v1:{v3} 
v2:{v3} 
v3:{} 

Betriebs Wie BFS Arbeiten Schritt für Schritt

Schritt 1:

Adjazenzlisten:

V  E 
v0: {v1,v2} mark, enqueue v0 
v1: {v3} 
v2: {v3} 
v3: {} 

Schritt 2:

Adjazenzlisten:

V  E 
v0: {v1,v2} dequeue v0;mark, enqueue v1,v2 
v1: {v3} 
v2: {v3} 
v3: {} 

Schritt 3:

Adjazenzlisten:

V  E 
v0: {v1,v2} 
v1: {v3} dequeue v1; mark,enqueue v3 
v2: {v3} 
v3: {} 

Schritt 4:

Adjazenzlisten:

V  E 
v0: {v1,v2} 
v1: {v3} 
v2: {v3} dequeue v2, check its adjacency list (v3 already marked) 
v3: {} 

Schritt 5:

Adjazenzlisten:

V  E 
v0: {v1,v2} 
v1: {v3} 
v2: {v3} 
v3: {} dequeue v3; check its adjacency list 

Step6:

Adjazenzlisten:

V  E 
v0: {v1,v2} |E0|=2 
v1: {v3} |E1|=1 
v2: {v3} |E2|=1 
v3: {}  |E3|=0 

Gesamtzahl der Schritte:

|V| + |E0| + |E1| + |E2| +|E3| == |V|+|E| 
4 + 2 + 1 + 1 + 0 == 4 + 4 
          8 == 8 

Angenommen, eine Adjazenzlisten-Darstellung, V ist die Anzahl der Scheitelpunkte, E die Anzahl der Kanten.

Jeder Scheitelpunkt wird höchstens einmal in die Warteschlange eingereiht und aus der Warteschlange entfernt.

Das Scannen für alle benachbarten Vertices dauert O (| E |) Zeit, da die Summe der Längen der Adjazenzlisten | E | ist.

Daher ergibt die Zeitkomplexität von BFS eine O (| V | + | E |) Zeitkomplexität.

Answer 4

I understood the part V+E in the complexity. 
But I have 2 questions 
1). V * Eaj should give 2E? 
(as it is the total no of edges accessed, and each edge is checked twice, by each of it ends) 

2) Also the complexity is V + E 
but in worst case we take E = V*(V-1)/2 
So V isn't required here as we could say we E = V²... 
Can't we say complexity O(E) only?