If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Analiza przeszukiwania wszerz (BFS)

Jak długo trwa przeszukiwanie wszerz grafu ze zbiorem wierzchołków V i zbiorem krawędzi E? Odpowiedź to czas o złożoności O(V+E).
Zobaczmy, co oznacza czas O(V+E). Załóżmy na chwilę, że |E||V|, co jest prawdą dla większości grafów, zwłaszcza dla tych, dla których używamy przeszukiwania wszerz. Zatem |V|+|E||E|+|E|=2|E|. Ponieważ ignorujemy stałe czynniki w notacji asymptotycznej widzimy, że kiedy |E||V|, O(V+E) naprawdę oznacza O(E). Jeśli jednak |E|<|V|, wtedy |V|+|E||V|+|V|=2|V|, zatem O(V+E) naprawdę oznacza O(V). Możemy połączyć oba przypadki, mówiąc, że O(V+E) naprawdę oznacza O(max(V,E)). Ogólnie, mając parametry x i y, wtedy O(x+y) naprawdę oznacza O(max(x,y)).
(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 wierzchołków. Graf spójny, w którym |E|=|V|1 nazywamy drzewem.)
Dlaczego przeszukiwanie grafu wszerz działa w czasie O(V+E)? Zainicjalizowanie odległości i przodków dla każdego wierzchołka zajmuje O(V) (właściwie Θ(V)) 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) 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.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.