Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Depth-first search (DFS) in C

Depth-first search (DFS) explores the next branch of a graph before returning to the remaining neighbors. The example demonstrates recursive traversal, visited-vertex marking, and a deterministic printing order.

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

Syntax

void dfs(int v);

Depth-first search (depth-first search, DFS) explores the next branch before returning to the remaining neighbors. Recursive traversal (recursive traversal) implements this pattern through function calls for unvisited neighbors; returning from a call resumes the previous loop. DFS itself does not specify when a vertex is processed; this example prints it upon discovery.

In the example, graph[v][u] represents a directed edge from v to u. The dfs function sets visited[v] before making further calls, so the cycle 0 → 1 → 3 → 0 does not reenter 0. Increasing u order produces 0, 1, 3, 2, 4, each on its own line. Every supplied index is within 0–N - 1.

Calling dfs(0) visits only vertices reachable from 0. To cover the entire graph, call dfs for each still-unvisited vertex. Reset visited before starting an independent traversal again.

With an adjacency matrix, a complete traversal takes O(V²) time; an adjacency-list representation allows O(V + E), where V and E are the vertex and edge counts. The visited array and call stack require O(V) auxiliary space. Deep recursion can exhaust the call stack; an explicit stack is an alternative. The repository context identifies C23 as a compiler flag but does not attest a production runtime.

Examples

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

Result

0
1
3
2
4

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources