Przeszukiwanie w głąb (DFS)
Przegląda graf, idąc jedną ścieżką tak głęboko, jak się da, a potem wraca do ostatniego rozwidlenia. Stos na ekranie to właśnie ta ścieżka.
- O(V + E)
- pamięć O(V)
- stos
V i E: liczba wierzchołków i krawędzi. O(V + E) oznacza, że każdy wierzchołek i każda krawędź są obsługiwane stałą liczbę razy.
Stos: kto ostatni wszedł, ten pierwszy wychodzi. DFS zawsze idzie dalej od wierzchołka, do którego dotarł ostatnio.
Inne pojęcia na tej stronie
- Wierzchołek: punkt grafu, tu narysowany jako kółko z literą.
- Krawędź: linia łącząca dwa wierzchołki. Tutaj można nią przejść w obie strony.
- Sąsiedzi: wierzchołki połączone z danym wierzchołkiem krawędzią. Są sprawdzani w kolejności alfabetycznej.
Spróbuj: Wybierz graf z cyklami. Każda przerywana krawędź prowadzi z powrotem do wierzchołka, który jest już na stosie albo jest gotowy. Taka krawędź zamyka cykl.
Jak to działa
DFS wywołuje sam siebie dla pierwszego sąsiada, którego jeszcze nie widział, potem dla pierwszego nowego sąsiada tego wierzchołka i tak dalej. Gdy wierzchołek nie ma już nowych sąsiadów, jego wywołanie się kończy, a DFS cofa się o krok i próbuje tam następnego sąsiada. Otwarte wywołania tworzą stos, który zawsze jest ścieżką od startu do bieżącego wierzchołka. Liczba przy wierzchołku mówi, w jakiej kolejności został odwiedzony.
Kiedy warto go użyć
DFS przydaje się, gdy trzeba sprawdzić, dokąd w ogóle da się dojść, znaleźć cykle, przejść labirynt albo ułożyć w kolejności zadania zależne od siebie. Najkrótszej drogi nie znajduje.