BFS — Breadth-First Search Algorithm Guide

What is Breadth-First Search?

Breadth-First Search (BFS) is a graph traversal technique that explores vertices level by level. Starting from a source vertex, it first visits all vertices at distance 1, then all vertices at distance 2, and so on. BFS uses a queue, so the earliest discovered vertex is processed first.

• Traversal idea: expand outward in layers from the source.
• Main data structure: queue (FIFO).
• Best known use: shortest path in an unweighted graph.
• Complexity: O(V + E) time and O(V) space.

Where BFS Fits in Graph Problems

BFS is the standard graph traversal technique when we care about distance in number of edges, level structure, or minimum hops. It is not just a way to visit nodes; it is the foundation of shortest path algorithms for unweighted graphs, level-order tree traversal, connected-component discovery, bipartite checking, and many grid-based search problems.

Core Intuition

Think of BFS like a wave spreading in water. The source vertex is the point where the wave begins. In the first step, the wave touches all immediate neighbors. In the next step, it reaches the neighbors of those neighbors. Because BFS always processes the current layer completely before moving deeper, the first time we reach a vertex, we have found the minimum number of edges needed to get there.

When BFS is a Good Choice

• When all edges have equal cost and we need the shortest path.
• When we need to process vertices layer by layer.
• When solving minimum-move problems in grids, mazes, or state spaces.
• When we need to know which vertices are at distance 1, 2, 3, and so on from a source.

BFS Algorithm Steps

1. Mark the source vertex as visited.
2. Insert the source vertex into the queue.
3. While the queue is not empty:
   • Remove the front vertex.
   • Process it.
   • For every unvisited neighbor, mark it visited and enqueue it.
4. Stop when the queue becomes empty.

Worked Example

Consider the graph with edges: 0-1, 0-2, 1-3, 1-4, 2-5. Start BFS from vertex 0.

BFS order: 0, 1, 2, 3, 4, 5. Distances from 0: dist[0]=0, dist[1]=1, dist[2]=1, dist[3]=2, dist[4]=2, dist[5]=2.

BFS Tree and Levels

As BFS runs, it forms a BFS tree. Each newly discovered vertex gets a parent, and all vertices discovered from the same distance belong to the same level.

• Level 0: the source vertex.
• Level 1: all vertices directly connected to the source.
• Level 2: all vertices two edges away from the source.
• In general, level k contains all vertices whose shortest distance from the source is k.

import java.util.*;

public class BFS {

    static int V;
    static List<List<Integer>> adj;

    static void buildGraph(int v) {
        V = v;
        adj = new ArrayList<>();
        for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
    }

    static void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);  // undirected graph
    }

    // BFS traversal - O(V + E)
    static void bfs(int src) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

        visited[src] = true;
        queue.offer(src);

        System.out.print("BFS order: ");
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        System.out.println();
    }

    // Shortest path distances in an unweighted graph
    static int[] shortestPath(int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, -1);

        Queue<Integer> queue = new LinkedList<>();
        dist[src] = 0;
        queue.offer(src);

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : adj.get(node)) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        buildGraph(6);
        addEdge(0, 1); addEdge(0, 2);
        addEdge(1, 3); addEdge(1, 4);
        addEdge(2, 5);

        bfs(0);  // 0 1 2 3 4 5

        int[] dist = shortestPath(0);
        System.out.println("Shortest distances from 0:");
        for (int i = 0; i < V; i++) {
            System.out.println("to " + i + " = " + dist[i]);
        }
    }
}

Why BFS Gives the Shortest Path

In an unweighted graph, every edge contributes the same cost: one step. BFS explores all vertices reachable in 1 step before any vertex reachable in 2 steps, all vertices reachable in 2 steps before any vertex reachable in 3 steps, and so on. Therefore, when a vertex is discovered for the first time, BFS has already found the minimum number of edges from the source to that vertex.

How to Reconstruct the Actual Path

To recover the actual shortest path, we store a parent for each vertex when it is first discovered.

• When BFS discovers vertex `v` from `u`, set `parent[v] = u`.
• After reaching the destination, move backward using the parent array.
• Reverse that sequence to obtain the path from source to destination.

This is useful because BFS itself tells us both the minimum distance and the structure of the shortest path tree.

Applications of BFS

• Shortest path in unweighted graphs: minimum hop count between two nodes.
• Level-order traversal in trees: visit nodes level by level.
• Connected components: run BFS from every unvisited vertex.
• Bipartite graph checking: alternate colors across levels.
• Web crawling: explore pages in expanding layers.
• Social networks: find all people within k degrees of connection.
• Grid problems: shortest moves in mazes, matrices, or chess boards.

BFS on Disconnected Graphs

If the graph is disconnected, a BFS starting from one source visits only the connected component containing that source. To traverse the whole graph, we repeat BFS from every unvisited vertex.

1. Loop through all vertices.
2. If a vertex is unvisited, start a new BFS from it.
3. Each BFS run covers exactly one connected component.

Multi-Source BFS

Sometimes we need the distance from the nearest source among several starting points. In that case, we can begin BFS with all sources already in the queue and distance 0 for each of them. This is called multi-source BFS.

It is common in problems like nearest hospital, nearest exit, nearest zero in a matrix, and spreading processes such as fire, infection, or signal propagation.

BFS for Bipartite Checking

A graph is bipartite if its vertices can be split into two groups such that no edge connects vertices in the same group. BFS helps by coloring alternate levels with opposite colors.

• Assign one color to the source.
• Assign the opposite color to all of its neighbors.
• If we ever find an edge connecting two vertices with the same color, the graph is not bipartite.

BFS Complexity Analysis

Weighted vs Unweighted Limitation

BFS works for shortest path only when every edge has equal cost. If one edge has weight 10 and another has weight 1, the path with fewer edges may not be the cheapest path. That is why weighted graphs need algorithms like Dijkstra or Bellman-Ford.

BFS vs DFS

Common Mistakes

• Marking a vertex visited too late, which can enqueue the same vertex multiple times.
• Using BFS for weighted shortest path problems where edges have different costs.
• Forgetting to run BFS from every unvisited vertex when the graph is disconnected.
• Confusing traversal order with path reconstruction; use a parent array if you need the actual path.
• Marking a vertex visited only after dequeuing it, which can cause duplicate queue entries.

Common Questions

• Can BFS be used on trees? Yes. Level-order traversal of a tree is exactly BFS.
• Does BFS always give the shortest path? Yes, but only in unweighted graphs.
• Can BFS detect cycles? Yes, with suitable visited/parent logic.
• Why use a queue? Because BFS must process older discoveries before deeper ones.

Key Takeaways

• BFS expands a graph in layers starting from a source.
• It uses a queue and a visited structure.
• It is the correct choice for shortest path in unweighted graphs.
• Its time complexity is linear in the size of the graph: O(V + E).
• Its layer structure makes it useful for shortest paths, levels, bipartite checking, and multi-source search.