DFS – przeszukiwanie w głąb (Depth‑First Search)

DFS (ang. Depth‑First Search) – algorytm przeszukiwania grafu, w którym zwiedzane są kolejne wierzchołki tak długo, jak to możliwe, zanim algorytm powróci i rozpocznie badanie kolejnych gałęzi. Jest to podstawowa technika wykorzystywana w wielu dziedzinach informatyki, w tym w algorytmice, grafach, drzewach oraz w problemach związanych z wyszukiwaniem i spójnością struktur.

Historia

Pierwsze formalne opracowanie metody przeszukiwania w głąb pojawiło się w latach 1940 w pracach Claude’a Shannona i Johna von Neumanna. Jeden z najwcześniejszych opisów algorytmu znajduje się w artykule Arthur'a Rosenfelda z 1948 roku, a w późniejszych dekadach DFS stał się miejscem badań w ramach złożoności obliczeniowej.

Zasada działania

DFS rozpoczyna się od wybranego wierzchołka (zwany „źródłem”) i przechodzi wzdłuż krawędzi ( krawędzi ) tak długo, aż nie będzie już nieodwiedzonych sąsiadów. Następnie algorytm cofa się (tzw. backtrack) do ostatniego wierzchołka, w którym istnieją jeszcze nieodwiedzone sąsiady, i kontynuuje proces.

Implementacja rekurencyjna

function DFS(v):
    visited[v] ← true
    for each u in Adjacent(v):
        if not visited[u]:
            DFS(u)

Rekurencyjna wersja wykorzystuje stos wywołań systemu (rekurencję) i jest często używana w demonstracjach algorytmicznych.

Implementacja iteracyjna

function DFS_iterative(start):
    stack ← empty stack
    stack.push(start)
    while not stack.empty():
        v ← stack.pop()
        if not visited[v]:
            visited[v] ← true
            for each u in Adjacent(v) in reverse order:
                if not visited[u]:
                    stack.push(u)

W wersji iteracyjnej algorytm korzysta ze stos jawnie, co eliminuje ryzyko przepełnienia stosu wywołań w przypadkach bardzo głębokich drzew.

Złożoność czasowa i pamięciowa

Dla grafu G = (V, E) o V wierzchołkach i E krawędziach, DFS ma:

Czas: O(|V| + |E|) – każdy wierzchołek i każda krawędź jest odwiedzany co najwyżej raz.
Pamięć: O(|V|) – potrzebna jest tablica visited oraz stos (rekurencyjny lub jawny) o maksymalnej wysokości równej liczbie wierzchołków w najgłębszej ścieżce.

Warianty i powiązane algorytmy

DFS i BFS – porównanie z Breadth‑First Search, które przeszukuje graf warstwa po warstwie.
Topologiczne sortowanie – można je uzyskać przy pomocy modyfikacji DFS w grafach acyklicznych skierowanych (DAG).
Silnie spójne składowe – algorytm Kosaraju oraz Tarjana opiera się na dwóch przebiegach DFS.
Mosty i punkty artykulacji – wykrywanie krytycznych krawędzi i wierzchołków przy użyciu algorytmu DFS z numerowaniem odkrycia i niskim czasem (low‑link).
Kompresja ścieżek (ang. path compression) w strukturach union‑find wykorzystuje technikę podobną do odwiedzania w głąb.

Zastosowania

DFS znajduje szerokie zastosowanie w:

Generowaniu labiryntów i rozwiązywaniu zagadek typu mazes.
Analizie grafów planujących w robotyce i GIS.
Wyznaczaniu cykli w grafach, np. wykrywanie cyklu w zależnościach modułów.
Rozwiązywaniu problemów z kopcowym podzbiorem, takich jak problem podzbioru.
Tworzeniu drzewek rozpinających (np. algorytm DFS z wyznaczaniem mostów).
Analizie programowania dynamicznego w strukturach drzewiastych, np. w algorytmie najdłuższej ścieżki w DAG.

Przykładowe problemy

W konkursach programistycznych i zadaniach edukacyjnych najczęściej pojawiają się problemy takie jak:

Sprawdzanie, czy graf jest drzewem.
Wyszukiwanie wszystkich cykli w grafie skierowanym.
Wyznaczanie liczby komponentów spójności.
Znajdowanie najgłębszego wierzchołka (tzw. deepest node) w drzewie.
Konstrukcja kompresji ścieżek w strukturze Union‑Find przy użyciu techniki przypominającej DFS.

Implementacje w językach programowania

W większości języków (np. Python, C++, Java) DFS można zaimplementować w kilku linijkach kodu, co czyni go doskonałym narzędziem dydaktycznym.

Powiązane pojęcia

Jeśli chcesz zgłębić tematy pokrewne, zobacz także:

DFS pozostaje jedną z fundamentów informatyki, będąc nie tylko prostą techniką przeszukiwania, ale także podstawą bardziej zaawansowanych metod analizujących struktury danych.