Graph BFS

Intuition

Drop a stone into a still pond. The ripple reaches every point one unit away before it reaches anything two units away. Breadth-first search (BFS) behaves the same way on a graph: starting from a source node it visits every node at distance 1, then every node at distance 2, and so on. Because nodes are discovered in order of how many edges separate them from the source, the first time BFS reaches a node it has already found the shortest route to it, as long as every edge counts the same.

The tool that enforces this ordering is a FIFO queue. Whatever is discovered first is expanded first, so the frontier never jumps ahead to a deeper level while a shallower one still has work. Swap the queue for a stack and you get depth-first behaviour instead, which is the subject of the sibling lesson on Graph DFS.

In interviews the graph is almost always given as an adjacency list: adj[u] holds the neighbors of u. That representation makes the cost of BFS proportional to the number of nodes plus the number of edges, which is the best you can hope for when every node might matter.

How it works step by step

1. Create a dist array filled with -1 (meaning unseen) and an empty queue.
2. Set dist[src] = 0 and push src. Marking happens now, at enqueue time, not when the node is popped.
3. While the queue is not empty, pop the front node u.
4. For each neighbor v in adj[u]: if dist[v] is still -1, set dist[v] = dist[u] + 1, remember parent[v] = u if you need the path, and push v.
5. When the queue empties, dist holds the fewest-edge distance to every reachable node; unreachable nodes are still -1.
6. To process the graph level by level (for example to return a list per level), read queue.size() at the start of each round and pop exactly that many nodes before moving on.

Dry run on a small graph

Undirected graph with 6 nodes and edges 0-1, 0-2, 1-3, 2-3, 2-4, 3-5, 4-5. Source is 0. The queue column shows the state after the action.

Notice step 3: node 3 is a neighbor of node 2, but it was already marked in step 2, so it is not pushed twice. If we had waited until pop time to mark nodes, 3 would sit in the queue twice and, on denser graphs, the queue could grow far beyond the node count.

Code

import java.util.*;

public class GraphBFS {
    // Fewest-edge distance from src to every node, -1 when unreachable.
    public static int[] shortestDistances(List<List<Integer>> adj, int src) {
        int n = adj.size();
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Deque<Integer> queue = new ArrayDeque<>();
        dist[src] = 0;                 // visited-on-enqueue
        queue.offer(src);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }
        return dist;
    }

    // Two-colour the graph level by level; a same-colour edge means not bipartite.
    public static boolean isBipartite(List<List<Integer>> adj) {
        int n = adj.size();
        int[] color = new int[n];      // 0 = uncoloured, 1 / -1 = the two sides
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;   // handles disconnected graphs
            color[s] = 1;
            Deque<Integer> queue = new ArrayDeque<>(List.of(s));
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : adj.get(u)) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        queue.offer(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

from collections import deque


def shortest_path(adj, src, target):
    """Return one fewest-edge path from src to target, or [] if none exists."""
    parent = {src: None}            # doubles as the visited set
    queue = deque([src])
    while queue:
        u = queue.popleft()
        if u == target:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1]
        for v in adj[u]:
            if v not in parent:
                parent[v] = u
                queue.append(v)
    return []


def levels(adj, src):
    """Group nodes by their BFS level."""
    seen, queue, result = {src}, deque([src]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            u = queue.popleft()
            level.append(u)
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    queue.append(v)
        result.append(level)
    return result


adj = [[1, 2], [0, 3], [0, 3, 4], [1, 2, 5], [2, 5], [3, 4]]
print(shortest_path(adj, 0, 5))   # [0, 1, 3, 5]
print(levels(adj, 0))             # [[0], [1, 2], [3, 4], [5]]

Time and space complexity

The V + E bound depends on the visited-on-enqueue rule. Each node enters the queue at most once, so the outer loop runs V times and the inner loops together touch every edge a constant number of times.

Edge cases

• Disconnected graph: a single BFS only reaches the source's component. Loop over all nodes and start a new BFS from every unvisited one when you need full coverage, as in the bipartite check.
• Source equals target: the distance is 0 and the path is just [src]; make sure you check before expanding.
• Self-loops and parallel edges: harmless, because the visited check ignores a node that is already marked.
• Directed graphs: follow only outgoing edges. A node can be reachable from A without A being reachable from it.
• Isolated source: the queue empties after one pop and every other distance stays -1.

Common mistakes

• Marking nodes as visited when they are popped instead of when they are pushed. The answer is still correct, but duplicates pile up in the queue and the run can degrade badly on dense graphs.
• Using a Java LinkedList or a Python list with pop(0). list.pop(0) is O(n) per call; use collections.deque or ArrayDeque.
• Applying BFS to weighted edges. BFS minimises the number of edges, not the total weight. Use Dijkstra's algorithm when weights differ.
• Forgetting that the level counter needs the queue.size() snapshot. Reading the size inside the loop changes as you push.
• Building the adjacency list for an undirected graph with only one direction of each edge.

Variations and when to use it

Reach for BFS whenever a problem says fewest moves, minimum steps, nearest, or level when every move costs the same. The bipartite check is BFS with colours instead of distances: an edge between two nodes of the same colour proves an odd cycle. 0-1 BFS handles graphs whose edges weigh only 0 or 1 by pushing 0-weight neighbors to the front of a deque and 1-weight neighbors to the back. Bidirectional BFS runs two frontiers from the source and the target and stops when they meet, which shrinks the search dramatically on graphs like Word Ladder. BFS on an implicit graph, where neighbors are generated on the fly, is the same algorithm; the grid version is covered in BFS on a grid.

Related LeetCode problems

• #399 Evaluate Division — treat each ratio as a weighted edge and BFS from the numerator, multiplying weights along the way.
• #785 Is Graph Bipartite? — the two-colour BFS from this lesson, run from every uncoloured node.
• #886 Possible Bipartition — build the dislike graph, then run the same bipartite check.
• #1129 Shortest Path with Alternating Colors — BFS over (node, last colour) states instead of plain nodes.
• #127 Word Ladder — words are nodes, one-letter changes are edges, and the answer is a BFS level count.
• #133 Clone Graph — BFS visits each node once while a hash map links originals to their copies.
• #1971 Find if Path Exists in Graph — the simplest reachability BFS on an adjacency list.

FAQ