Depth-first search

Overview

Depth-first search dives down one path until it can go no further, then backtracks and tries the next option. Implemented recursively, it visits a vertex, marks it, and calls itself on each not-yet-visited neighbour. A visited array is what keeps it from looping forever when the graph has cycles.

Why it matters

DFS is the backbone of graph reachability: 'which components can this failure spread to?', 'is there any dependency path from A to B?', 'can this state reach a winning state?'. It also underlies cycle detection, topological sort, and connected-components — all later lessons in this track.

Core concepts

Visited set. One boolean per vertex; mark on entry, never revisit.

Reachable set. The vertices DFS marks starting from src are exactly those reachable from src (including src itself).

Recursion = an implicit stack. Each call frame remembers where to resume; an explicit stack gives the same traversal iteratively.

Directed edges. Follow only i→j; do not treat the matrix as symmetric unless the graph is undirected.

Syntax notes

#include <stdlib.h>

/* recursive DFS - mark BEFORE recursing */
static void dfs(const int *adj, int n, int v, int *vis) {
    vis[v] = 1;                                  /* mark first, or cycles loop forever */
    for (int u = 0; u < n; u++)
        if (adj[v*n + u] && !vis[u])
            dfs(adj, n, u, vis);
}

int reachable_count(const int *adj, int n, int src) {
    int *vis = calloc((size_t)n, sizeof *vis);   /* zeroed = nothing visited yet */
    if (!vis) return -1;
    dfs(adj, n, src, vis);
    int c = 0;
    for (int i = 0; i < n; i++) c += vis[i];     /* src itself is included */
    free(vis);
    return c;
}

Key points:

• vis[v] = 1 must happen before the neighbour loop; marking afterwards lets a cycle recurse forever.
• calloc gives the all-unvisited starting state for free.
• The reachable set always includes the source, so the count is at least 1.

Lesson

Depth-first search follows one path as far as it goes before backing up. A visited array stops it from looping forever on cycles. DFS answers the fundamental questions of reachability: which vertices can I get to from here, and is there any path from A to B? It is naturally recursive — visit a vertex, then recurse into each unvisited neighbour.

Code examples

#include <stdio.h> static int n=5; static int adj[25]={ 0,1,1,0,0, 0,0,0,1,0, 0,0,0,1,0, 0,0,0,0,0, 0,0,0,0,0 }; static void dfs(int v,int vis){ vis[v]=1; for(int u=0;u<n;u++) if(adj[vn+u]&&!vis[u]) dfs(u,vis); } int main(void){ for(int s=0;s<n;s++){ int vis[5]={0}; dfs(s,vis); int cnt=0; for(int i=0;i<n;i++) cnt+=vis[i]; printf("from %d: reachable=%d can reach 3? %s\n", s, cnt, vis[3]?"yes":"no"); } return 0; }

Line by line

Common mistakes

Forgetting to mark a vertex visited before recursing, which loops forever on a cycle. Treating directed edges as undirected. Not counting src itself in the reachable set.

Debugging tips

Compiler errors and warnings:

• -Wunused-parameter if you forget to pass n through to the recursion.
• No warning for a missing vis mark — it manifests only at runtime.

Runtime symptoms:

• Stack overflow / hang on a cyclic graph. You marked the vertex after the loop, or not at all. Mark on entry.
• The count is one too low. You counted neighbours rather than visited vertices — the source is part of its own reachable set.
• A vertex is visited twice. The !vis[u] test is missing before the recursive call.
• Reachability is symmetric when it should not be. You treated a directed matrix as undirected; DFS follows adj[v][u] only.
• Crash on a large graph. Recursion depth equals the number of vertices in the worst case; a 100,000-vertex path graph exhausts the stack.

Technique: print the vertex on entry to dfs. The order shows you immediately whether the traversal is going deep (correct) or wide, and repeated vertices reveal a missing mark.

Memory safety

• Mark before recursing. This is a safety property, not just correctness: without it a cyclic graph recurses until the stack is exhausted, which is an unrecoverable crash.
• Recursion depth equals path length. In the worst case that is n frames; for large graphs convert to an explicit stack, which also gives you control over the memory used.
• vis must be exactly n entries and zeroed. calloc is correct here; malloc leaves garbage that reads as "already visited", silently truncating the traversal.
• Validate src. vis[src] with an out-of-range source writes outside the allocation.
• Free on every path, including the early error return.
• const int *adj documents that the traversal does not modify the graph — useful when a caller shares one matrix across several searches.

Real-world uses

Concrete uses: Detecting whether a dependency can be reached from a root, garbage-collection mark phases, maze and puzzle solving, topological ordering, finding connected components, and cycle detection all build on DFS. Compilers use it for control-flow analysis; package managers use it to resolve dependency closures.

Professional best practices:

Beginner:

• Mark the vertex on entry, before any recursion.
• Remember the source counts as reachable from itself.

Intermediate:

• Use an explicit stack for large or untrusted graphs so depth is bounded by heap rather than the call stack.
• Pass the visited array in rather than allocating it per call when running many searches over the same graph — reuse and clear it.
• DFS finds a path, not the shortest one; reach for BFS when distance matters.

Practice tasks

1. (Beginner) Reachable count. Implement int reachable_count(const int *adj, int n, int src) including the source. Example: in the demo graph, 4 from vertex 0. Concepts: visited array, marking on entry.

2. (Beginner) Path existence. Implement int has_path(const int *adj, int n, int src, int dst) returning 1 when src == dst. Concepts: early exit, reflexive reachability.

3. (Intermediate) Iterative DFS. Rewrite the traversal with an explicit stack array and confirm it visits the same set. Concepts: removing recursion depth limits.

4. (Intermediate) Record the order. Output the vertices in the order DFS first visits them, and explain why it differs from BFS order. Concepts: traversal order.

Summary

Depth-first search follows one path as far as it goes, then backtracks, and a visited array is what keeps it from looping forever on a cycle — the mark must be set on entry, before the neighbour loop, or a cyclic graph recurses until the stack is exhausted. The set of vertices DFS marks starting from a source is exactly that source's reachable set, and it always includes the source itself. Allocate the visited array with calloc so "unvisited" is the default, validate the source index, and remember that recursion depth can reach the vertex count — use an explicit stack for large graphs, and use BFS instead when you need shortest distances rather than mere reachability.

Practice with these exercises

• Count reachable vertices (DFS)
• Does a path exist? (DFS)