Breadth-first search

Overview

Breadth-first search explores a graph in expanding rings: first the source, then everything one edge away, then everything two edges away, and so on. A FIFO queue enforces that order. Because vertices come out in non-decreasing distance, the first time BFS reaches a vertex is via a shortest (fewest-edge) path.

Why it matters

On an unweighted graph, BFS is the shortest-path algorithm — minimum hops between two computers on a network, fewest moves in a puzzle, degrees of separation in a social graph. Its layer-by-layer structure also answers 'how many things are exactly k steps away?'.

Core concepts

Queue, not stack. FIFO order is what makes the traversal breadth-first.

Distance array. Initialise to −1 (unseen); set dist[neighbour]=dist[current]+1 on first discovery.

Shortest hops. The value in dist[dst] at the end is the minimum edge count; −1 means unreachable.

Layers. All vertices sharing a dist value form one BFS layer.

Why the queue must be FIFO. Replacing it with a stack turns the traversal into DFS, which still visits every reachable vertex but assigns distances along whatever path it happened to take first — those numbers are not minima. The ring-by-ring expansion is the entire reason BFS answers shortest-path questions.

Syntax notes

#include <stdlib.h>

/* shortest hop distance from src to every vertex; -1 = unreachable */
int *bfs_dist(const int *adj, int n, int src) {
    int *dist = malloc((size_t)n * sizeof *dist);
    int *q    = malloc((size_t)n * sizeof *q);      /* each vertex enqueued at most once */
    if (!dist || !q) { free(dist); free(q); return NULL; }
    for (int i = 0; i < n; i++) dist[i] = -1;       /* -1 means 'not seen yet' */
    int head = 0, tail = 0;
    dist[src] = 0; q[tail++] = src;
    while (head < tail) {                           /* FIFO - this is what makes it BFS */
        int v = q[head++];
        for (int u = 0; u < n; u++)
            if (adj[v*n + u] && dist[u] < 0) {      /* unseen -> first time is shortest */
                dist[u] = dist[v] + 1;
                q[tail++] = u;
            }
    }
    free(q);
    return dist;                                    /* caller frees */
}

Key points:

• dist[u] < 0 doubles as the visited test — a vertex is labelled exactly once.
• The queue needs at most n slots because each vertex is enqueued once.
• FIFO (head++) is essential; using a stack turns this into DFS and the distances become meaningless.

Lesson

Breadth-first search expands outward in rings of increasing distance using a queue. Because it reaches every vertex in non-decreasing distance order, BFS gives the shortest path in an unweighted graph — the fewest edges from source to target. Track a dist[] array (−1 = unseen) and every vertex is labelled with its hop distance as it is dequeued.

Code examples

#include <stdio.h> int main(void){ int n=6; int adj[36]={ 0,1,1,0,0,0, 0,0,0,1,0,0, 0,0,0,1,0,0, 0,0,0,0,1,0, 0,0,0,0,0,1, 0,0,0,0,0,0 }; int src=0, dist[6], q[6], head=0,tail=0; for(int i=0;i<n;i++) dist[i]=-1; dist[src]=0; q[tail++]=src; while(head<tail){ int v=q[head++]; for(int u=0;u<n;u++) if(adj[v*n+u]&&dist[u]<0){ dist[u]=dist[v]+1; q[tail++]=u; } } for(int i=0;i<n;i++) printf("hop distance %d -> %d = %d\n", src, i, dist[i]); return 0; }

Line by line

Common mistakes

Using a stack (that gives DFS, not shortest paths). Overwriting a distance already set — only the first, smallest one counts. Forgetting the unreachable (−1) case.

Debugging tips

Compiler errors and warnings:

• -Wmaybe-uninitialized if you malloc dist and forget the -1 fill loop.
• No warning for using a stack instead of a queue.

Runtime symptoms:

• Distances are wrong but plausible. You used a stack (LIFO) instead of a queue — that is DFS, and it finds a path rather than the shortest.
• A vertex gets a larger distance than it should. You overwrote an existing label; the dist[u] < 0 check must guard the assignment.
• Infinite loop or queue overflow. The same vertex is enqueued repeatedly because it is not labelled at enqueue time. Label it when you push, not when you pop.
• Unreachable vertices report distance 0. You initialised dist with calloc; 0 is a real distance (the source), so the sentinel must be -1.
• Crash on the queue. It must hold n entries; enqueuing a vertex more than once overflows it — another symptom of labelling too late.

Technique: print (vertex, distance) as each item is dequeued. The distances must be non-decreasing; if they jump around, the container is not FIFO.

Memory safety

• Label at enqueue, not at dequeue. If a vertex can be pushed twice, the n-slot queue overflows and writes past its allocation — a real buffer overflow, not just a wrong answer.
• Sentinel choice. -1 for "unseen" because 0 is a legitimate distance. calloc here would make the source indistinguishable from unreached vertices.
• Two allocations, one failure path. Check both and free whatever succeeded before returning — the code above frees dist and q together on failure.
• Ownership. Returning dist transfers ownership to the caller; document that, or the array leaks. The internal queue is freed before returning.
• Validate src before writing dist[src].
• No recursion, so unlike DFS there is no stack-depth limit — an advantage on very large graphs.

Real-world uses

Concrete uses: Shortest route in an unweighted network, degrees of separation in a social graph, minimum moves in a puzzle (Rubik's cube, sliding tiles), web crawling by depth, network broadcast hop counts, and flood fill by distance. BFS is also the basis for computing a graph's diameter and for level-order traversal of trees.

Professional best practices:

Beginner:

• Use -1 (not 0) as the unseen sentinel.
• Label vertices as you enqueue them.

Intermediate:

• Use BFS whenever edges are unweighted and you need distance; Dijkstra is only necessary once weights appear.
• For very large graphs consider a bit-array for the visited set to cut memory.
• Bidirectional BFS (searching from both ends) can dramatically reduce the explored frontier when you need a single source-target distance.

Practice tasks

1. (Beginner) Hop distance. Implement int bfs_distance(const int *adj, int n, int src, int dst) returning 0 for src == dst and -1 when unreachable. Concepts: queue, distance labels.

2. (Beginner) Count at a distance. Implement int count_at_distance(const int *adj, int n, int src, int d). Concepts: BFS layers.

3. (Intermediate) Prove FIFO matters. Swap the queue for a stack and show the distances become wrong. Concepts: why BFS gives shortest paths.

4. (Intermediate) Reconstruct the path. Keep a parent[] array and print the actual shortest route from src to dst. Concepts: path reconstruction.

Summary

Breadth-first search expands outward in rings using a FIFO queue, so the first time it reaches a vertex is always by a shortest path — which is why BFS answers unweighted shortest-distance questions and DFS does not. Initialise distances to -1 rather than 0, since 0 is a real distance for the source, and label each vertex as you enqueue it: labelling late allows a vertex to be pushed twice, which overflows an n-slot queue. Anything still -1 when the queue empties is unreachable. BFS uses no recursion, so unlike DFS it has no stack-depth limit on large graphs.

Practice with these exercises

• Shortest hop distance (BFS)
• Count vertices at distance d