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.
- czas O(V + E)
- pamięć O(V)
- używa stosu
Co to znaczy?
- 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.
- Kolejka: kto pierwszy wszedł, ten pierwszy wychodzi. BFS zawsze bierze wierzchołek, który czeka najdłużej.
- Stos: kto ostatni wszedł, ten pierwszy wychodzi. DFS zawsze idzie dalej od wierzchołka, do którego dotarł ostatnio.
- 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.
- na stosie
- bieżący
- gotowy
- krawędź drzewa przeszukiwania
- pominięta krawędź
Zacznij od wierzchołka A. Naciśnij Odtwórz albo przechodź przez przeszukiwanie krok po kroku.
Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.
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.