Przeszukiwanie grafu w głąb
Znamy już algorytmy wyszukujące w grafach cykle Hamiltona, Euleracykle Hamiltona, Eulera czy też spójne składowespójne składowe. Wszystkie te typy algorytmów miały jedną wspólną cechę: każdy z nich albo wprost korzystał z algorytmu przeszukiwania grafu w głąb albo był jego modyfikacją. Ten rodzaj przeszukiwania znajduje zastosowanie również w wielu innych algorytmach grafowych. W tym e‑materiale sprawdzimy, jak dokładnie przebiega procedura przeszukiwania grafu w głąb oraz poznamy jej zasady.
Przeanalizujesz działanie przeszukiwania grafu w głąb i zapis tego algorytmu za pomocą pseudokodu.
Określisz złożoność pamięciową i czasową algorytmu DFS.
Wyjaśnisz, w jakich szczególnych przypadkach przeszukiwanie grafu w głąb może okazać się niekompletne.