Offensive Security Researcher & Quantum Cryptography Analyst

Breadth-First Search (BFS) Algorithm: Working, Explanation, and Graph Traversal

Abdul Wahab Junaid
breadth first search algorithm and working of this algorithm

breadth first search algorithm and working of this algorithm

I think of breadth-first search as the algorithm that explores a graph the way ripples spread across water — outward, one layer at a time, from a single starting point. It systematically visits all neighbors of a node before moving on to the neighbors of those neighbors, which makes it the natural choice whenever I need to find the shortest path in an unweighted graph or explore a structure level by level. BFS underlies an enormous number of practical systems, from network broadcast protocols to social network “degrees of separation” features, and understanding it well has always felt foundational to understanding graph algorithms in general.

History and Background

Breadth-first search traces its formal origins to Edward F. Moore, who described the technique in 1959 as a method for finding the shortest path out of a maze. Around the same time, Konrad Zuse, a pioneer of early computing, had independently discovered a similar approach for path-finding in graphs, though his work was not published until much later and did not immediately influence the field the way Moore’s did. BFS was subsequently formalized as a fundamental graph traversal method during the growth of graph theory and algorithm analysis in the 1960s and 70s, and it remains one of the two canonical traversal strategies (alongside depth-first search) taught in every algorithms curriculum.

Problem Statement

I need a systematic way to visit every reachable node in a graph starting from a given source, while guaranteeing that I discover nodes in order of increasing distance (measured in number of edges) from that source. This matters most when I need the shortest path in an unweighted graph, since BFS naturally guarantees the first time I reach any node is via the shortest possible path in terms of edge count.

Core Concepts

How It Works

I carry out BFS through these steps:

  1. I start by placing the source node into a queue and marking it as visited.
  2. While the queue is not empty, I dequeue the front node and process it (e.g., print it, record its distance).
  3. For every unvisited neighbor of the dequeued node, I mark it as visited and enqueue it.
  4. I repeat this process until the queue is empty, at which point every node reachable from the source has been visited.

Working Principle

The reason BFS explores level by level comes directly from the FIFO nature of the queue. Since I always enqueue neighbors of the current node at the back of the queue, and I always process nodes from the front, all nodes at distance k from the source get processed — and their neighbors (distance k+1) enqueued — before any node at distance k+1 is itself dequeued and processed. This ordering guarantee is what makes BFS ideal for shortest-path calculations: by the time I first discover a node, I have necessarily found it via the shortest possible route, since any shorter route would have caused it to be discovered at an earlier level.

Mathematical Foundation

If a graph has V vertices and E edges, BFS visits every vertex exactly once and examines every edge exactly once (or twice, in an undirected graph, since each edge is checked from both endpoints), giving:

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

For the shortest-path property, I can express the distance guarantee formally: if $d(s, v)$ denotes the true shortest-path distance (in edges) from source s to vertex v, BFS guarantees that the first time v is dequeued:

$$\text{distance}[v] = d(s, v)$$

This can be proven by induction on the levels of the BFS tree, since each level strictly increases the frontier’s distance from the source by exactly one edge.

Diagrams

flowchart TD
    A[Start: source node] --> B[Enqueue source, mark visited]
    B --> C{Queue empty?}
    C -->|No| D[Dequeue front node]
    D --> E[Process node]
    E --> F[For each unvisited neighbor]
    F --> G[Mark neighbor visited, enqueue it]
    G --> C
    C -->|Yes| H[Output: All reachable nodes visited]

Pseudocode

BFS(Graph, source)
    create empty queue Q
    mark source as visited
    enqueue source into Q

    while Q is not empty
        node = dequeue Q
        process(node)

        for each neighbor in Graph.adjacent(node)
            if neighbor is not visited
                mark neighbor as visited
                enqueue neighbor into Q

Step-by-Step Example

I will run BFS on this graph starting at node S: S — A, S — B, A — C, A — D, B — E, C — F

Step 1: Enqueue S, mark visited. Queue: [S]

Step 2: Dequeue S, process it. Neighbors A and B are unvisited → mark and enqueue both. Queue: [A, B]

Step 3: Dequeue A, process it. Neighbors C and D are unvisited → mark and enqueue both. Queue: [B, C, D]

Step 4: Dequeue B, process it. Neighbor E is unvisited → mark and enqueue. Queue: [C, D, E]

Step 5: Dequeue C, process it. Neighbor F is unvisited → mark and enqueue. Queue: [D, E, F]

Step 6: Dequeue D, process it. No unvisited neighbors. Queue: [E, F]

Step 7: Dequeue E, process it. No unvisited neighbors. Queue: [F]

Step 8: Dequeue F, process it. No unvisited neighbors. Queue: []

Traversal order: S, A, B, C, D, E, F

Time Complexity

Space Complexity

BFS requires O(V) space for the visited set, O(V) in the worst case for the queue (if, for example, the graph is a star shape with one central node connected to all others), and O(V) if I also track parent pointers to reconstruct shortest paths. Overall, this gives a space complexity of O(V).

Correctness Analysis

I prove BFS’s correctness in two parts. First, termination and completeness: since each node is enqueued at most once (guarded by the visited check) and the queue only shrinks by dequeuing, the algorithm must terminate, and every node reachable from the source is guaranteed to be enqueued at some point due to the neighbor-exploration step covering every edge. Second, the shortest-path property: I prove by induction on distance k that all nodes at distance k from the source are enqueued before any node at distance k+1. This holds because a node at distance k+1 can only be discovered as the neighbor of some node at distance k, and since I process the queue in FIFO order, all distance-k nodes are dequeued (and their distance-(k+1) neighbors enqueued) before any distance-(k+1) node is itself dequeued and expanded further.

Advantages

Disadvantages

Applications

Implementation in C

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

#define MAX_VERTICES 100

// Simple adjacency list representation
int adjList[MAX_VERTICES][MAX_VERTICES];
int adjCount[MAX_VERTICES];
int visited[MAX_VERTICES];

// Simple queue implementation using an array
int queue[MAX_VERTICES];
int front = 0, rear = 0;

void enqueue(int val) {
    queue[rear++] = val;
}

int dequeue() {
    return queue[front++];
}

int isQueueEmpty() {
    return front == rear;
}

// BFS traversal starting from a given source vertex
void bfs(int source, int numVertices) {
    for (int i = 0; i < numVertices; i++) visited[i] = 0;

    visited[source] = 1;
    enqueue(source);

    printf("BFS traversal order: ");
    while (!isQueueEmpty()) {
        int node = dequeue();
        printf("%d ", node);

        for (int i = 0; i < adjCount[node]; i++) {
            int neighbor = adjList[node][i];
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                enqueue(neighbor);
            }
        }
    }
    printf("\n");
}

// Add an undirected edge between u and v
void addEdge(int u, int v) {
    adjList[u][adjCount[u]++] = v;
    adjList[v][adjCount[v]++] = u;
}

int main() {
    int numVertices = 6;  // S=0, A=1, B=2, C=3, D=4, E=5 (F omitted for brevity)

    addEdge(0, 1); // S-A
    addEdge(0, 2); // S-B
    addEdge(1, 3); // A-C
    addEdge(1, 4); // A-D
    addEdge(2, 5); // B-E

    bfs(0, numVertices);

    return 0;
}

Sample Input and Output

Input: Graph with edges S-A, S-B, A-C, A-D, B-E, starting BFS from S (vertex 0)

Output: BFS traversal order: 0 1 2 3 4 5

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version