Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Przeszukiwanie w głąb (DFS) w C

Przeszukiwanie w głąb (depth-first search, DFS) bada kolejną gałąź grafu przed powrotem do pozostałych sąsiadów. Przykład pokazuje przechodzenie rekurencyjne, oznaczanie odwiedzonych wierzchołków i deterministyczną kolejność wypisywania.

Wersja: C23; repository compiler flag, production runtime not attested

Składnia

void dfs(int v);

Przeszukiwanie w głąb (depth-first search, DFS) zagłębia się w kolejną gałąź, zanim wróci do pozostałych sąsiadów. Przechodzenie rekurencyjne (recursive traversal) realizuje ten schemat przez wywołania funkcji dla nieodwiedzonych sąsiadów; powrót z wywołania wznawia poprzednią pętlę. Sama nazwa DFS nie określa momentu przetwarzania wierzchołka; przykład wypisuje go przy odkryciu.

W przykładzie graph[v][u] oznacza krawędź skierowaną z v do u. Funkcja dfs ustawia visited[v] przed dalszymi wywołaniami, więc cykl 0 → 1 → 3 → 0 nie powoduje ponownego wejścia do 0. Rosnąca kolejność u daje wynik 0, 1, 3, 2, 4, każdy w osobnym wierszu. Wszystkie przekazywane indeksy należą do zakresu 0–N - 1.

Wywołanie dfs(0) odwiedza tylko wierzchołki osiągalne z 0. Aby objąć cały graf, należy uruchamiać dfs dla każdego jeszcze nieodwiedzonego wierzchołka. Przed niezależnym ponownym przejściem trzeba wyzerować visited.

Dla macierzy sąsiedztwa pełne przejście ma koszt czasowy O(V²); reprezentacja listowa pozwala uzyskać O(V + E), gdzie V i E oznaczają liczby wierzchołków i krawędzi. Tablica odwiedzin i stos wywołań wymagają O(V) pamięci pomocniczej. Duża głębokość rekurencji może wyczerpać stos; alternatywą jest jawny stos. Kontekst repozytorium wskazuje C23 jako flagę kompilatora, nie potwierdza jednak środowiska produkcyjnego.

Przykłady

#include <stdio.h>

enum { N = 5 };

static const int graph[N][N] = {
    {0, 1, 1, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 0, 0, 1},
    {1, 0, 0, 0, 0},
    {0, 0, 0, 0, 0}
};
static int visited[N] = {0};

static void dfs(int v)
{
    visited[v] = 1;
    printf("%d\n", v);

    for (int u = 0; u < N; ++u) {
        if (graph[v][u] && !visited[u]) {
            dfs(u);
        }
    }
}

int main(void)
{
    dfs(0);
    return 0;
}

Wynik

0
1
3
2
4

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła