Przeszukiwanie grafu
Z Wikipedii
Przeszukiwanie grafu lub inaczej przechodzenie grafu to czynność polegająca na odwiedzeniu w jakiś usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacji. Często podczas przejścia grafu rozwiązujemy już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu.
Powszechnie stosuje się dwie podstawowe metody przeszukiwania grafów:
- przeszukiwanie wszerz (BFS)
- przeszukiwanie w głąb (DFS)
Odrębnym zagadnieniem jest przechodzenie drzew, zwłaszcza binarnych które jest niewątpliwie przeszukiwaniem grafu. Wyróżnia się trzy metody przechodzenia drzew, przy czym ostatnia metoda dotyczy tylko drzew binarnych:
[edytuj] Linki zewnętrzne
http://www.algorytm.org/index.php?option=com_content&task=view&id=98&Itemid=28