Depth-first search in C

The same graph, a recursive walk, and a different visiting order.

#define MAX_NODES 8

static void visit(const int graph[MAX_NODES][MAX_NODES], int nodes, int node,
                  int *visited, int *order, int *seen) {
    visited[node] = 1;
    order[(*seen)++] = node;

    for (int next = 0; next < nodes; next++) {
        if (graph[node][next] && !visited[next]) {
            visit(graph, nodes, next, visited, order, seen);
        }
    }
}

int dfs(const int graph[MAX_NODES][MAX_NODES], int nodes, int start,
        int *order) {
    int visited[MAX_NODES] = {0};
    int seen = 0;
    visit(graph, nodes, start, visited, order, &seen);
    return seen;
}

How it works

1. Recursion replaces the explicit queue with the call stack.
2. The visited array is what stops the cycles.
3. Post-order collection gives a topological ordering.

Keywords and builtins used here

• const
• dfs
• for
• if
• int
• return
• static
• visit
• void

The run, in numbers

Lines

21

Characters to type

517

Tokens

165

Three-star pace

105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 94 seconds.

Type this snippet

Step 2 of 2 in Graphs, step 16 of 20 in Data structures & algorithms.

← Previous Next →