Przeszukiwanie w głąb

Przeszukiwanie w głąb (DFS)

Przeszukiwanie w głąb (ang. Depth-first search, DFS) to algorytm wykorzystywany do przeszukiwania grafów. Działa on poprzez badanie wszystkich krawędzi wychodzących z danego wierzchołka, a następnie powraca do wierzchołka, z którego został odwiedzony.

Przykład działania algorytmu

Rozpoczynając przeszukiwanie od wierzchołka A w grafie, węzły zostaną odwiedzone w następującej kolejności: A, B, D, F, E, C, G.

Algorytm DFS

Podstawowe funkcje algorytmu można zdefiniować w następujący sposób:

function VisitNode(u):
    oznacz u jako odwiedzony
    dla każdego wierzchołka v w sąsiedztwie u:
        jeżeli v nieodwiedzony:
            VisitNode(v)

function DepthFirstSearch(Graf G):
    dla każdego wierzchołka u w G:
        oznacz u jako nieodwiedzony
    dla każdego wierzchołka u w G:
        jeżeli u nieodwiedzony:
            VisitNode(u)

Właściwości algorytmu

Złożoność pamięciowa

Złożoność pamięciowa algorytmu DFS jest znacznie mniejsza w porównaniu do przeszukiwania wszerz. Wymaga on zapamiętania jedynie ścieżki od korzenia do bieżącego węzła.

Złożoność czasowa

Złożoność czasowa DFS zależy od liczby wierzchołków (|V|) oraz krawędzi (|E|) w grafie, wynosząc O(|V| + |E|).

Zupełność (kompletność)

Algorytm jest zupełny dla skończonych drzew, jednak w przypadku grafów nieskończonych nie gwarantuje znalezienia rozwiązania.

Zastosowania algorytmu

• Wyznaczanie silnych spójnych składowych w grafach skierowanych.
• Sortowanie topologiczne w grafach acyklicznych.
• Sprawdzanie istnienia ścieżki między wierzchołkami (badanie spójności grafu).

Implementacja

Przykłady implementacji algorytmu można znaleźć na stronie Wikibooks.