Przeszukiwanie w głąb (DFS)
Algorytm przeglądania grafu, który schodzi jak najgłębiej, zanim zawróci — zaimplementowany ze stosem (lub rekurencją).
Do wykrywania cykli używa się trzech kolorów: biały (nieodwiedzony), szary (w trakcie, na stosie rekurencji), czarny (zakończony). Krawędź prowadząca do szarego wierzchołka oznacza cykl. DFS jest potrzebny do sortowania topologicznego, wykrywania spójności (Tarjan) i generowania labiryntów.
Złożoność czasowa O(V+E), pamięciowa w najgorszym razie O(V) (głęboka rekurencja). Konkurent: BFS (kolejka FIFO zamiast stosu, znajduje najkrótszą ścieżkę w grafie nieważonym). Przy głębokich grafach zaleca się wersję iteracyjną, by uniknąć przepełnienia stosu.