CKTIS / C
Pretraživanje u dubinu (DFS) u C-u
Pretraživanje u dubinu (DFS) istražuje sljedeću granu grafa prije povratka preostalim susjedima. Primjer prikazuje rekurzivni obilazak, označavanje posjećenih vrhova i deterministički redoslijed ispisa.
Verzija: C23; repository compiler flag, production runtime not attested
Sintaksa
void dfs(int v);Pretraživanje u dubinu (depth-first search, DFS) istražuje sljedeću granu prije povratka preostalim susjedima. Rekurzivni obilazak (recursive traversal) provodi taj obrazac pozivima funkcije za neposjećene susjede; nakon povratka iz poziva nastavlja se prethodna petlja. Sam DFS ne određuje kada se vrh obrađuje; ovaj ga primjer ispisuje pri otkrivanju.
U primjeru graph[v][u] predstavlja usmjereni brid od v do u. Funkcija dfs postavlja visited[v] prije daljnjih poziva pa ciklus 0 → 1 → 3 → 0 ne uzrokuje ponovni ulazak u 0. Rastući redoslijed u daje 0, 1, 3, 2, 4, svaki u zasebnom retku. Svi zadani indeksi nalaze se u rasponu 0–N - 1.
Poziv dfs(0) posjećuje samo vrhove dostupne iz 0. Za obilazak cijelog grafa pozovite dfs za svaki još neposjećeni vrh. Ponovno postavite visited prije novog neovisnog obilaska.
Uz matricu susjedstva, potpuni obilazak zahtijeva vrijeme O(V²); prikaz popisima susjedstva omogućuje O(V + E), pri čemu su V i E broj vrhova i bridova. Polje posjećenih i stog poziva zahtijevaju O(V) pomoćnog prostora. Duboka rekurzija može iscrpiti stog poziva; izričiti stog je alternativa. Kontekst repozitorija navodi C23 kao zastavicu prevoditelja, ali ne potvrđuje produkcijsko okruženje.
Primjeri
#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;
}
Rezultat
0 1 3 2 4
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.