Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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.

Zdroje