CKTIS / C
Iskanje v globino (DFS) v C
Iskanje v globino (DFS) razišče naslednjo vejo grafa, preden se vrne k preostalim sosedom. Primer prikazuje rekurzivni prehod, označevanje obiskanih vozlišč in deterministični vrstni red izpisa.
Različica: C23; repository compiler flag, production runtime not attested
Sintaksa
void dfs(int v);Iskanje v globino (depth-first search, DFS) razišče naslednjo vejo, preden se vrne k preostalim sosedom. Rekurzivni prehod (recursive traversal) ta vzorec izvede s klici funkcije za neobiskane sosede; po vrnitvi iz klica se nadaljuje prejšnja zanka. DFS sam po sebi ne določa, kdaj se vozlišče obdela; ta primer ga izpiše ob odkritju.
V primeru graph[v][u] predstavlja usmerjeno povezavo od v do u. Funkcija dfs nastavi visited[v] pred nadaljnjimi klici, zato cikel 0 → 1 → 3 → 0 ne povzroči ponovnega obiska vozlišča 0. Naraščajoči vrstni red u da izpis 0, 1, 3, 2, 4, vsakega v svoji vrstici. Vsi podani indeksi so v območju 0–N - 1.
Klic dfs(0) obišče samo vozlišča, dosegljiva iz 0. Za prehod čez celoten graf pokličite dfs za vsako še neobiskano vozlišče. Pred ponovnim neodvisnim prehodom ponastavite visited.
Pri matriki sosednosti celoten prehod zahteva čas O(V²); predstavitev s seznami sosednosti omogoča O(V + E), pri čemer V in E pomenita število vozlišč in povezav. Polje obiskanih vozlišč in sklad klicev zahtevata O(V) dodatnega prostora. Globoka rekurzija lahko izčrpa sklad klicev; alternativa je izrecni sklad. Kontekst repozitorija navaja C23 kot zastavico prevajalnika, vendar ne potrjuje produkcijskega okolja.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.