Przeszukiwanie wszerz
Z Wikipedii, wolnej encyclopedia
Przeszukiwanie wszerz (ang. breadth-first search, BFS) – jeden z najprostszych algorytmów przeszukiwania grafu. Przechodzenie grafu rozpoczyna się od zadanego wierzchołka s i polega na odwiedzeniu wszystkich osiągalnych z niego wierzchołków. Wynikiem działania algorytmu jest drzewo przeszukiwania wszerz o korzeniu w s, zawierające wszystkie wierzchołki osiągalne z s. Do każdego z tych wierzchołków prowadzi dokładnie jedna ścieżka z s, która jest jednocześnie najkrótszą ścieżką w grafie wejściowym. Algorytm działa prawidłowo zarówno dla grafów skierowanych jak i nieskierowanych[1].
Szybkie fakty Rodzaj, Struktura danych ...
Kolejność odwiedzania węzłów | |
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Pamięciowa |
|
Zamknij
|
Ten artykuł od 2018-09-16 może zawierać twórczość własną lub niezweryfikowane informacje. |