KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

Diepte-eerst zoeken (DFS) in C

Diepte-eerst zoeken (DFS) verkent de volgende tak van een graaf voordat het terugkeert naar de overige buren. Het voorbeeld laat recursieve doorloop, markering van bezochte knopen en een deterministische afdrukvolgorde zien.

Versie: C23; repository compiler flag, production runtime not attested

Syntax

void dfs(int v);

Diepte-eerst zoeken (depth-first search, DFS) verkent de volgende tak voordat het terugkeert naar de overige buren. Recursieve doorloop (recursive traversal) voert dit patroon uit door de functie aan te roepen voor niet-bezochte buren; na terugkeer uit een aanroep wordt de vorige lus hervat. DFS bepaalt op zichzelf niet wanneer een knoop wordt verwerkt; dit voorbeeld drukt de knoop af zodra deze wordt ontdekt.

In het voorbeeld stelt graph[v][u] een gerichte verbinding van v naar u voor. De functie dfs stelt visited[v] in voordat zij verdere aanroepen doet. Daardoor leidt de cyclus 0 → 1 → 3 → 0 niet tot een nieuwe bezoeking van 0. De oplopende volgorde van u levert 0, 1, 3, 2, 4 op, elk op een eigen regel. Alle opgegeven indices vallen binnen 0–N - 1.

De aanroep dfs(0) bezoekt alleen knopen die bereikbaar zijn vanaf 0. Roep dfs aan voor elke nog niet bezochte knoop om de hele graaf te doorlopen. Zet visited terug voordat je een onafhankelijke doorloop opnieuw start.

Met een adjacentiematrix kost een volledige doorloop O(V²) tijd; een representatie met adjacentielijsten maakt O(V + E) mogelijk, waarbij V en E het aantal knopen en verbindingen aangeven. De visited-array en aanroepstack gebruiken O(V) extra ruimte. Diepe recursie kan de aanroepstack uitputten; een expliciete stack is een alternatief. De repositorycontext noemt C23 als compileroptie, maar bevestigt geen productieomgeving.

Voorbeelden

#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;
}

Resultaat

0
1
3
2
4

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen