Graph traversal: BFS and DFS

Introduction

To traverse a graph is to visit every vertex you can reach from a start vertex. Unlike a tree, a graph can have cycles, so every traversal keeps track of which vertices it has already seen. Both examples use this graph:

  0 --- 1 --- 3
  |           |
  2 --- 4 --- 5

Once a graph is stored, nearly every question about it starts the same way: visit what can be reached. Finding the fewest stops between two stations, or whether two computers are connected, are both traversals underneath.

How it works

Depth-first search (DFS)

#include <stdio.h>
#define N 6

int adj[N][N];
int visited[N];

void add_edge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1;
}

void dfs(int u) {
    visited[u] = 1;
    printf("%d ", u);
    for (int v = 0; v < N; v++)
        if (adj[u][v] && !visited[v]) dfs(v);
}

int main(void) {
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
    add_edge(2, 4);
    add_edge(3, 5);
    add_edge(4, 5);
    dfs(0);
    printf("\n");
    return 0;
}

DFS goes as deep as it can along one path, and backtracks when it is stuck. Recursion gives it a stack for free: the call stack. Watch the frames: 0 → 1 → 3 → 5 → 4 → 2, and then every call returns.

With an adjacency matrix, as here, both are O(n²), because each vertex scans a whole row.

To count the connected components of a graph, run DFS from every vertex that is not visited yet; each run finds one component.

Syntax

int queue[N], front = 0, rear = 0;

queue[rear++] = start;           // join the queue
while (front < rear) {
    int u = queue[front++];      // leave the queue
    /* look at each neighbour of u */
}

Example

#include <stdio.h>
#define N 6

int adj[N][N];

void add_edge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1;
}

int main(void) {
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
    add_edge(2, 4);
    add_edge(3, 5);
    add_edge(4, 5);
    int dist[N];
    for (int i = 0; i < N; i++) dist[i] = -1;   // -1: not seen yet
    int queue[N], front = 0, rear = 0;
    dist[0] = 0;
    queue[rear++] = 0;
    while (front < rear) {
        int u = queue[front++];
        printf("visit %d (distance %d)\n", u, dist[u]);
        for (int v = 0; v < N; v++) {
            if (adj[u][v] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue[rear++] = v;
            }
        }
    }
    return 0;
}

BFS visits vertices in rings: the start, then everything 1 edge away, then 2 edges away, and so on. A queue keeps the order: take the front vertex, and enqueue each neighbour not seen yet.

Here dist[v] is -1 for "not seen", so it also works as the visited mark. Because BFS reaches each vertex by the fewest possible edges, dist ends up holding the shortest path length (in edges) from 0 to every vertex. Watch queue, front and rear as vertices join and leave.

Line by line

1. adj is an adjacency matrix, and add_edge sets both directions.
2. Every dist starts at -1, meaning "not seen yet".
3. Vertex 0 is given distance 0 and put in the queue.
4. Each time round the loop, u is taken from the front and printed with its distance.
5. Each neighbour that has not been seen gets a distance one more than u, and joins the queue.
6. Because front only moves forward and each vertex joins once, the loop ends after visiting all that can be reached.

Expected result

visit 0 (distance 0)
visit 1 (distance 1)
visit 2 (distance 1)
visit 3 (distance 2)
visit 4 (distance 2)
visit 5 (distance 3)

In the real world

Navigation apps, friend suggestions and web crawlers are all built on traversals. Garbage collectors in languages such as Java traverse the graph of objects to find the ones no longer in use.

Common mistakes

• Marking a vertex visited when it is taken out of the queue instead of when it is put in: it can be enqueued twice.
• Forgetting the visited check in DFS: on a cycle it recurses forever.
• Assuming one BFS reaches every vertex: a disconnected graph needs a new start for each component.

Best practices

• Mark a vertex when it enters the queue, never later.
• Loop over every vertex when the graph might be disconnected.
• Choose BFS for fewest edges, and DFS when any order will do.

Summary

Breadth-first search uses a queue to visit vertices in order of distance, which also gives the fewest edges to each. Depth-first search goes deep first, using a stack or recursion. Both need a visited mark, and both cost O(n + m) with adjacency lists.

Mark lesson complete