Analiza przeszukiwania wszerz (BFS)

Jak długo trwa przeszukiwanie wszerz grafu ze zbiorem wierzchołków $V$V i zbiorem krawędzi $E$E? Odpowiedź to czas o złożoności $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis.

Zobaczmy, co oznacza czas $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis. Załóżmy na chwilę, że $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, co jest prawdą dla większości grafów, zwłaszcza dla tych, dla których używamy przeszukiwania wszerz. Zatem $|V| + |E| \leq |E| + |E| = 2 \cdot |E|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, E, vertical bar. Ponieważ ignorujemy stałe czynniki w notacji asymptotycznej widzimy, że kiedy $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis naprawdę oznacza $O(E)$O, left parenthesis, E, right parenthesis. Jeśli jednak $|E| < |V|$vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar, wtedy $|V| + |E| \leq |V| + |V| = 2 \cdot |V|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, V, vertical bar, plus, vertical bar, V, vertical bar, equals, 2, dot, vertical bar, V, vertical bar, zatem $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis naprawdę oznacza $O(V)$O, left parenthesis, V, right parenthesis. Możemy połączyć oba przypadki, mówiąc, że $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis naprawdę oznacza $O(\max(V,E))$O, left parenthesis, \max, left parenthesis, V, comma, E, right parenthesis, right parenthesis. Ogólnie, mając parametry $x$x i $y$y, wtedy $O(x+y)$O, left parenthesis, x, plus, y, right parenthesis naprawdę oznacza $O(\max(x,y))$O, left parenthesis, \max, left parenthesis, x, comma, y, right parenthesis, right parenthesis.

(Zauważ, że graf jest spójny Jeśli istnieje ścieżka z każdego wierzchołka do wszystkich innych wierzchołków. Aby graf był spójny musi posiadać co najmniej $|V|-1$vertical bar, V, vertical bar, minus, 1 wierzchołków. Graf spójny, w którym $|E| = |V|-1$vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1 nazywamy drzewem.)

Dlaczego przeszukiwanie grafu wszerz działa w czasie $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis? Zainicjalizowanie odległości i przodków dla każdego wierzchołka zajmuje $O(V)$O, left parenthesis, V, right parenthesis (właściwie $\Theta(V)$\Theta, left parenthesis, V, right parenthesis) czasu. Każdy wierzchołek jest odwiedzany co najwyżej raz, ponieważ tylko za pierwszym razem, gdy jest osiągany jego odległość posiada wartość null, zatem każdy wierzchołek jest dodany do kolejki co najwyżej raz. Ponieważ przeglądamy krawędzie wychodzące z wierzchołka jedynie, gdy badamy dany wierzchołek, każda krawędź jest sprawdzana co najwyżej dwa razy, raz dla każdego wierzchołka z którym się łączy. Zatem przeszukiwanie grafu wszerz zajmuje $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis czasu odwiedzając wszystkie wierzchołki.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.