BFS on graphs

Breadth-first search (BFS) explores a graph in expanding “rings” from a source: process the source, then all vertices at distance 1, then distance 2, and so on. A queue stores the current frontier; a visited flag stops infinite loops on cycles. On an unweighted graph, the first time you reach a vertex from the source is along a shortest path (minimum edge count).

1) Idea

FIFO order guarantees that vertices are peeled by nondecreasing hop count from the start (when edges are unweighted). DFS does not give that guarantee.

Source s = 0          Layer 0:  0
       |             Layer 1:  1, 2
   1 — 0 — 2          Layer 2:  3, 4  (example shape)

2) Algorithm

To traverse the whole graph (all components), repeat from every vertex with visited[i]==0.

3) Unweighted shortest path

Maintain dist[v] as above (or -1 / ∞ for unreachable). Then dist[t] equals the minimum number of edges from s to t. To print the path, store parent[v] when first discovering v, then walk backward from t.

4) Example in C (adjacency list)

Undirected graph: 0—1, 0—2, 1—3, 2—4. Uses a fixed-size adjacency matrix for simplicity (same logic as lists).

#include <stdio.h>
#include <string.h>

#define V 5
int adj[V][V];       /* set symmetric 1s for undirected edges */
/* e.g. 0-1,0-2,1-3,2-4: link (0,1)(1,0)(0,2)(2,0)(1,3)(3,1)(2,4)(4,2) */
int visited[V];
int dist[V];

void bfs(int start) {
    int q[V], front = 0, rear = 0;
    memset(visited, 0, sizeof visited);
    visited[start] = 1;
    dist[start] = 0;
    q[rear++] = start;

    while (front < rear) {
        int u = q[front++];
        for (int v = 0; v < V; v++) {
            if (adj[u][v] && !visited[v]) {
                visited[v] = 1;
                dist[v] = dist[u] + 1;
                q[rear++] = v;
            }
        }
    }
}

With an adjacency list, the inner loop runs in O(degree(u)); total time remains O(V + E). For large sparse graphs, prefer lists over scanning full rows of a matrix.

5) Complexity and directed graphs

• Time: O(V + E) with adjacency lists; O(V²) if you scan an entire adjacency matrix row per vertex.
• Space: O(V) for visited, queue, and auxiliary arrays.
• Directed: follow outgoing arcs only when building neighbors of u; BFS semantics unchanged.

Queue mechanics are covered in the queue tutorial; this page assumes FIFO behavior—see also BFS using a queue for another worked example.

6) Trace example (same graph as the code)

Below is the BFS traversal for the sample graph used above: undirected edges 0–1, 0–2, 1–3, 2–4, starting from vertex 0. Queue is shown front → rear; dist[] uses ∞ for “not reached yet.” Neighbors of each u are scanned in increasing vertex index v (as in the nested for loop in the listing).

Final dist[] after BFS

BFS traversal order (visit sequence)