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.