CKTIS / C
Prehľadávanie do hĺbky (DFS) v C
Prehľadávanie do hĺbky (DFS) preskúma ďalšiu vetvu grafu, než sa vráti k ostatným susedom. Príklad ukazuje rekurzívny priechod, označovanie navštívených vrcholov a deterministické poradie výpisu.
Verzia: C23; repository compiler flag, production runtime not attested
Syntax
void dfs(int v);Prehľadávanie do hĺbky (depth-first search, DFS) preskúma ďalšiu vetvu, než sa vráti k ostatným susedom. Rekurzívny priechod (recursive traversal) realizuje tento postup volaniami funkcie pre nenavštívených susedov; po návrate z volania pokračuje predchádzajúci cyklus. Samotné DFS neurčuje, kedy sa vrchol spracuje; tento príklad ho vypíše pri objavení.
V príklade graph[v][u] predstavuje orientovanú hranu z v do u. Funkcia dfs nastaví visited[v] pred ďalšími volaniami, takže cyklus 0 → 1 → 3 → 0 nespôsobí opätovné navštívenie 0. Vzostupné poradie u vytvorí výstup 0, 1, 3, 2, 4, každý na samostatnom riadku. Všetky zadané indexy sú v rozsahu 0–N - 1.
Volanie dfs(0) navštívi iba vrcholy dosiahnuteľné z 0. Ak chcete prejsť celý graf, zavolajte dfs pre každý dosiaľ nenavštívený vrchol. Pred novým nezávislým priechodom vynulujte visited.
Pri matici susednosti má úplný priechod časovú zložitosť O(V²); reprezentácia zoznamami susedov umožňuje O(V + E), kde V a E označujú počet vrcholov a hrán. Pole navštívených vrcholov a zásobník volaní vyžadujú O(V) pomocnej pamäte. Hlboká rekurzia môže vyčerpať zásobník volaní; alternatívou je explicitný zásobník. Kontext repozitára uvádza C23 ako príznak kompilátora, nepotvrdzuje však produkčné prostredie.
Prí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ýsledok
0 1 3 2 4
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.