Motywacja

DFS przeszukuje graf, wybierając ścieżkę i podążając nią tak daleko, jak to możliwe, a następnie cofając się do ostatniego wierzchołka z nieodwiedzonym sąsiadem.

Dlaczego warto poznać DFS?

• Podstawowy: stanowi podstawę wykrywania cykli, sortowania topologicznego, wyznaczania składowych spójnych i wielu innych algorytmów.
• Prosty i wydajny: działa w czasie O(V + E), korzystając ze stosu (lub rekurencji) oraz oznaczeń odwiedzonych wierzchołków.
• Wszechstronny: to samo przejście pozwala odpowiedzieć na pytania takie jak „czy te dwa wierzchołki są połączone?” i „z ilu oddzielnych części składa się graf?”

Aby wyniki były przewidywalne, zawsze odwiedzamy sąsiadów wierzchołka w kolejności rosnącej.