CKTIS / C
Prohledávání do hloubky (DFS) v C
Prohledávání do hloubky (DFS) prozkoumá další větev grafu, než se vrátí k ostatním sousedům. Příklad ukazuje rekurzivní průchod, označování navštívených vrcholů a deterministické pořadí výpisu.
Verze: C23; repository compiler flag, production runtime not attested
Syntaxe
void dfs(int v);Prohledávání do hloubky (depth-first search, DFS) prozkoumá další větev, než se vrátí k ostatním sousedům. Rekurzivní průchod (recursive traversal) tento postup realizuje voláním funkce pro nenavštívené sousedy; po návratu z volání pokračuje předchozí cyklus. Samotné DFS neurčuje, kdy se vrchol zpracuje; tento příklad jej vypíše při objevení.
V příkladu graph[v][u] představuje orientovanou hranu z v do u. Funkce dfs nastaví visited[v] před dalšími voláními, takže cyklus 0 → 1 → 3 → 0 nezpůsobí opětovné navštívení 0. Vzestupné pořadí u vytvoří výstup 0, 1, 3, 2, 4, každý na samostatném řádku. Všechny předané indexy jsou v rozsahu 0–N - 1.
Volání dfs(0) navštíví pouze vrcholy dosažitelné z 0. Chcete-li projít celý graf, zavolejte dfs pro každý dosud nenavštívený vrchol. Před novým nezávislým průchodem nastavte visited znovu na nulu.
U matice sousednosti má úplný průchod časovou složitost O(V²); reprezentace seznamy sousedů umožňuje O(V + E), kde V a E označují počet vrcholů a hran. Pole navštívených vrcholů a zásobník volání vyžadují O(V) pomocné paměti. Hluboká rekurze může vyčerpat zásobník volání; alternativou je explicitní zásobník. Kontext repozitáře uvádí C23 jako příznak kompilátoru, nepotvrzuje však produkční prostředí.
Příklady
#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;
}
Výsledek
0 1 3 2 4
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.