Breadth-First Search: Ripples in a Pond

Ripples

Drop a stone in a pond: the ripple reaches everything 1 step away, then 2 steps, then 3. Breadth-first search (BFS) explores a graph the same way, using a queue – just like level order in trees (Module 12). The one new thing: graphs can have loops, so we mark nodes as visited.

Because BFS reaches nodes in order of distance, the first time it reaches a node is along the fewest edges:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int n = 6;
        ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        int[][] roads = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}};
        for (int[] r : roads) { g.get(r[0]).add(r[1]); g.get(r[1]).add(r[0]); }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);                 // -1 = not visited yet
        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        dist[1] = 0;
        queue.offer(1);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : g.get(cur)) {
                if (dist[next] == -1) {        // first visit = shortest
                    dist[next] = dist[cur] + 1;
                    queue.offer(next);
                }
            }
        }
        for (int city = 1; city <= n; city++) {
            System.out.println("city " + city + ": " + dist[city] + " hops");
        }
    }
}

Output

city 1: 0 hops
city 2: 1 hops
city 3: 1 hops
city 4: 2 hops
city 5: 3 hops
city 6: 4 hops

Every node is added to the queue once and every edge is looked at twice (once from each end): O(n + m).

Common mistake: Marking a node visited when you take it out of the queue instead of when you put it in. The same node can then be added many times – slower, and sometimes wrong.

Remember: Fewest steps in a graph where every edge counts the same? That's BFS.