Depth-first search

Eight vertices in two pieces, searched from vertex 0. Watch the search run as deep as it can, then back up, one call at a time.

⋯29void dfs(int u, int from)30{31    seen[u] = true;32    disc_order[ndisc] = u;33    ndisc++;34    for (const struct enode *e = adj[u]; e != NULL; e = e->next) {35        if (!seen[e->to])36            dfs(e->to, u);37        else if (e->to != from)38            cycle = true;39    }40    fin_order[nfin] = u;41    nfin++;42}⋯51    int components = 0;52    for (int u = 0; u < V; u++) {53        if (!seen[u]) {54            dfs(u, -1);55            components++;56        }57    }58    printf("discovered:");59    for (int i = 0; i < ndisc; i++)60        printf(" %d", disc_order[i]);61    printf("\nfinished:");62    for (int i = 0; i < nfin; i++)63        printf(" %d", fin_order[i]);64    printf("\n%d components, cycle %d\n", components, cycle);65    for (int u = 0; u < V; u++) {

Deep before wide

Breadth-first search spreads out from its start one layer at a time. Depth-first search does the opposite: from each vertex it follows one unexplored edge straight away, and keeps going until it reaches a vertex with nothing new around it. Only then does it back up to the last vertex that still has an unexplored edge, and goes deep again from there.

Backing up needs a memory of the way back. Recursion gives it for free: each call is one vertex of the current path, and returning is backing up.

The code and its cost

The recursion

void dfs(int u, int from)
{
    seen[u] = true;
    disc_order[ndisc] = u;
    ndisc++;
    for (const struct enode *e = adj[u]; e != NULL; e = e->next) {
        if (!seen[e->to])
            dfs(e->to, u);
        else if (e->to != from)
            cycle = true;
    }
    fin_order[nfin] = u;
    nfin++;
}

dfs(u, from) marks u as seen, then walks u’s list. For each neighbour not yet seen it calls itself, and that call does not return until everything it can reach is seen. The second argument, from, is the vertex u was reached from. The cards in the picture are these calls: at any moment the column is exactly the path from the start to where the search stands.

Discovery and finishing

A vertex is discovered when its call starts and finished when its call returns. The two orders differ:

discovered: 0 1 2 4 3 5 6 7
finished: 3 5 4 2 1 0 7 6

The finishing order is not the discovery order reversed. Vertex 3 is discovered fifth but finishes first: when the search reaches it, both its neighbours, 1 and 4, are already seen, so its call has nothing to do. A vertex finishes only after every vertex discovered from it has finished, so 0, the start, finishes last of its piece.

The cost

Each vertex’s call runs once, because seen stops a second call, and each call walks its vertex’s list once. That is V calls and 2E list nodes in all, O(V + E). DFS does not find shortest routes: it reached 3 along 0, 1, 2, 4, 3, four edges, though the edge path 0, 1, 3 takes two.

Components

A search from one vertex sees only the vertices it can reach: one connected component, one piece of the graph. main starts a fresh search from every vertex still unseen and counts the starts:

for (int u = 0; u < V; u++) {
    if (!seen[u]) {
        dfs(u, -1);
        components++;
    }
}

Here the search from 0 sees 0 to 5, and the one from 6 sees 6 and 7: two components. Each start makes its own tree of calls.

Cycles

In an undirected graph, a seen neighbour is either the vertex the search just came from, along the same edge, or another way back to a vertex already on the search: a cycle. The first mark comes in dfs(2, 1): neighbour 0 is seen and is not 2’s parent, 1, so the edges 0–1, 1–2 and 2–0 close a triangle. The program prints cycle 1.

An explicit stack

The recursion can be replaced by a stack of vertices, as in traversals with a stack or a queue. dfs-stack.c pushes the start, then pops a vertex, skips it if it is already seen, and otherwise marks it and pushes its whole list:

stack[top] = s;
top++;
while (top > 0) {
    top--;
    int u = stack[top];
    if (seen[u])
        continue;
    seen[u] = true;
    printf(" %d", u);
    for (const struct enode *e = adj[u]; e != NULL; e = e->next) {
        stack[top] = e->to;
        top++;
    }
}

It prints discovered: 0 2 4 5 3 1 6 7. Pushing a list in its order puts its largest neighbour on top, so the stack goes to 2 before 1. A singly linked list cannot be walked backwards cheaply, so the two programs visit in different orders. Both are depth-first, and neither is the one right order.

The stack version has one more use. A deep graph, such as a path of a million vertices, makes a million nested calls and overflows the call stack; an array of vertices does not.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic dfs.c -o dfs
./dfs
gcc -std=c11 -Wall -Wextra -pedantic dfs-stack.c -o dfs-stack
./dfs-stack

Worked example

Times on one clock. Count discoveries and finishes on one counter, 1 to 16. Each vertex gets two times, (discovered, finished): 0 (1, 12), 1 (2, 11), 2 (3, 10), 4 (4, 9), 3 (5, 6), 5 (7, 8), 6 (13, 16), 7 (14, 15). Every vertex’s interval sits inside the interval of the vertex that called it, as the calls nest.

Remove the edge 1–2. The triangle opens, but a cycle remains: 0, 1, 3, 4, 2 and back to 0. DFS still prints cycle 1.

A tree. A connected graph of V vertices with V − 1 edges and no cycle is a tree. DFS never meets a seen vertex other than the one it came from, and prints cycle 0.

Two checks. Which vertex finishes first, and why? (3: both its neighbours are already seen.) How many components are there if the edge 4–5 is removed? (3: 4, 5 and 7.)

Where it’s used

Mazes. Generating a maze by carving deep passages and backing up, and solving one by trying a passage and backing up at each dead end.

Regions in images. Finding every pixel joined to a clicked one, one connected region at a time.

Circular dependencies. Finding a cycle among tasks that wait on each other, as topological order does next.

Other graph algorithms. Finding the bridges of a network, or its strongly connected parts, starts with a depth-first search and its times.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.