Offensive Security Researcher & Quantum Cryptography Analyst

Breadth-First Search (BFS) Algorithm: Comprehensive Explanation and Implementation

Abdul Wahab Junaid
Breadth-First Search (BFS) - Comprehensive Explanation

Breadth-First Search (BFS) Algorithm: Comprehensive Explanation and Implementation

Introduction

When I first started exploring graph algorithms, Breadth-First Search was one of the earliest ones I got comfortable with, and I still think it’s the right place to start. BFS is a traversal algorithm that explores a graph layer by layer, starting from a source vertex and visiting every vertex at distance 1 before moving on to distance 2, then distance 3, and so on. This “wave-like” expansion is what makes BFS so useful: it naturally finds the shortest path (in terms of number of edges) from a source to every other reachable vertex in an unweighted graph.

I use BFS whenever I need to answer questions like “what’s the minimum number of steps to get from A to B” or “which nodes are reachable within k hops.” It shows up everywhere from network broadcasting to social network analysis to solving sliding puzzle games.

History and Background

BFS doesn’t have a single flashy origin story the way some named algorithms do. It emerged from early work in graph theory and maze-solving procedures. The technique is often traced back to Konrad Zuse in the late 1940s, who described a maze-solving algorithm using breadth-first principles in his (at the time unpublished) work on the Plankalkül programming language. It was independently rediscovered by Edward F. Moore in 1959, who used it to find the shortest path out of a maze, and by C. Y. Lee in 1961 in the context of wire routing for circuit design (which is why some older texts call it “Lee’s algorithm”). Over time, BFS became a standard building block taught alongside DFS in every algorithms curriculum, formalized in the classic treatment by Cormen, Leiserson, Rivest, and Stein (CLRS) in Introduction to Algorithms.

Problem Statement

Given a graph G = (V, E) and a source vertex s, I want to visit every vertex reachable from s in order of increasing distance (number of edges) from s, and typically I also want to record that distance and a way to reconstruct the shortest path to each vertex.

Core Concepts

How It Works

  1. Start at the source vertex, mark it visited, and set its distance to 0.
  2. Push the source into a queue.
  3. While the queue is not empty, pop the front vertex u.
  4. For every neighbor v of u that hasn’t been visited yet, mark v visited, set its distance to distance[u] + 1, set its predecessor to u, and push v into the queue.
  5. Repeat until the queue is empty.

Because I always add new vertices to the back of the queue and always process from the front, vertices are guaranteed to be processed in non-decreasing order of distance from the source.

Working Principle

The key insight behind BFS is that a FIFO queue enforces strict ordering by discovery time, and discovery time corresponds exactly to shortest distance in an unweighted graph. Every vertex at distance d gets fully expanded (all its neighbors examined) before any vertex at distance d+1 is expanded. This is what guarantees correctness: by the time I pop a vertex u with distance d, I know for certain that d is the shortest possible distance to u, because any shorter path would have already caused u to be discovered earlier.

Mathematical Foundation

For an unweighted graph, the distance function computed by BFS satisfies:

$$\delta(s, v) = \min { , |P| : P \text{ is a path from } s \text{ to } v , }$$

where |P| is the number of edges in path P. BFS computes this exactly, and it can be proven inductively: assume all vertices at distance ≤ d have correct distance labels; then any vertex v at true distance d+1 must have at least one neighbor at distance d (otherwise its distance would not be d+1), and that neighbor will discover v during its expansion, correctly labeling it d+1.

The total work done is bounded by:

$$T(V, E) = O(V + E)$$

since every vertex is enqueued once, and every edge is examined at most once (or twice for undirected graphs, once per direction).

Diagrams

flowchart TD
    A[Start: enqueue source, mark visited] --> B{Queue empty?}
    B -- No --> C[Dequeue vertex u]
    C --> D[For each neighbor v of u]
    D --> E{v visited?}
    E -- No --> F[Mark v visited, set distance, enqueue v]
    E -- Yes --> D
    F --> D
    D --> B
    B -- Yes --> G[Done]

Pseudocode

BFS(G, s):
    for each vertex v in G.V:
        visited[v] = false
        distance[v] = infinity
        predecessor[v] = NIL

    visited[s] = true
    distance[s] = 0
    Q = empty queue
    enqueue(Q, s)

    while Q is not empty:
        u = dequeue(Q)
        for each v in G.adj[u]:
            if visited[v] == false:
                visited[v] = true
                distance[v] = distance[u] + 1
                predecessor[v] = u
                enqueue(Q, v)

Step-by-Step Example

Suppose I have this undirected graph:

1 - 2
1 - 3
2 - 4
3 - 4
4 - 5

Starting BFS from vertex 1:

  1. Visit 1, distance 0. Queue: [1]
  2. Dequeue 1. Neighbors 2, 3 are unvisited → distance 1. Queue: [2, 3]
  3. Dequeue 2. Neighbor 4 is unvisited → distance 2. Queue: [3, 4]
  4. Dequeue 3. Neighbor 4 already visited, skip. Queue: [4]
  5. Dequeue 4. Neighbor 5 unvisited → distance 3. Queue: [5]
  6. Dequeue 5. No unvisited neighbors. Queue: []

Final distances: 1→0, 2→1, 3→1, 4→2, 5→3.

Time Complexity

Space Complexity

Correctness Analysis

I can prove BFS correctness formally using the loop invariant that at the start of each iteration, the queue contains vertices with distances that are non-decreasing and span at most two consecutive distance values. Combined with the inductive argument in the Mathematical Foundation section, this guarantees that when a vertex is dequeued, its recorded distance is indeed the shortest possible distance from the source. Since every reachable vertex is eventually enqueued (because BFS explores all edges from every dequeued vertex), completeness also holds — every reachable vertex will be visited.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct {
    int adj[MAX_VERTICES][MAX_VERTICES]; /* adjacency matrix */
    int numVertices;
} Graph;

void initGraph(Graph *g, int n) {
    g->numVertices = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g->adj[i][j] = 0;
}

void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1;
    g->adj[v][u] = 1; /* remove this line for a directed graph */
}

void bfs(Graph *g, int source) {
    int visited[MAX_VERTICES] = {0};
    int distance[MAX_VERTICES];
    int predecessor[MAX_VERTICES];
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    for (int i = 0; i < g->numVertices; i++) {
        distance[i] = -1;
        predecessor[i] = -1;
    }

    visited[source] = 1;
    distance[source] = 0;
    queue[rear++] = source;

    while (front < rear) {
        int u = queue[front++];
        printf("Visited: %d\n", u);

        for (int v = 0; v < g->numVertices; v++) {
            if (g->adj[u][v] == 1 && !visited[v]) {
                visited[v] = 1;
                distance[v] = distance[u] + 1;
                predecessor[v] = u;
                queue[rear++] = v;
            }
        }
    }

    printf("\nVertex\tDistance\tPredecessor\n");
    for (int i = 0; i < g->numVertices; i++)
        printf("%d\t%d\t\t%d\n", i, distance[i], predecessor[i]);
}

int main(void) {
    Graph g;
    initGraph(&g, 5); /* vertices 0..4, matching 1..5 from the example, zero-indexed */

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 4);

    bfs(&g, 0);

    return 0;
}

Sample Input and Output

Input: Graph with edges (0,1), (0,2), (1,3), (2,3), (3,4); source = 0.

Output:

Visited: 0
Visited: 1
Visited: 2
Visited: 3
Visited: 4

Vertex  Distance    Predecessor
0       0           -1
1       1           0
2       1           0
3       2           1
4       3           3

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version