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.