Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje