Breadth-first Search

Breadth-first search (or simply BFS) is another widely used graph traversal algorithm. Unlike in depth-first search, in BFS you traverse nodes that are closer to the starting node sooner than those that are more distant:

void bfs(int startNode, List<List<Integer>> graph, int distance[]) {
    final int INF = Integer.MAX_VALUE;
    Arrays.fill(distance, INF);
    
    Queue<Integer> queue = new LinkedList<>();
    distance[startNode] = 0;
    queue.add(startNode);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        
        for (int neighbour : graph.get(node))
            if (distance[neighbour] == INF) {
                distance[neighbour] = distance[node] + 1;
                queue.add(neighbour);
            }
    }
}

Note how we use queue to maintain the right order of nodes in BFS. Also, here we don't use recursion.

After BFS is done, we produce the distance array which for every node of a graph indicates how many edges away it is from the starting node. In case some node is unreachable from the starting node, its distance will be infinity (in our code above, Integer.MAX_VALUE).

Let's say our graph has N nodes and M edges. BFS will visit or go along each one of them at most once, so the runtime of BFS will be O(N + M) (similar to depth-first search).

We can traverse our example graph above with BFS like this:

void bfs(int startNode, List<List<Integer>> graph, int distance[]) {
    final int INF = Integer.MAX_VALUE;
    Arrays.fill(distance, INF);
    
    Queue<Integer> queue = new LinkedList<>();
    distance[startNode] = 0;
    queue.add(startNode);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        
        for (int neighbour : graph.get(node))
            if (distance[neighbour] == INF) {
                distance[neighbour] = distance[node] + 1;
                queue.add(neighbour);
            }
    }
}

final int N = 4;
List<List<Integer>> graph = Arrays.asList(
    Arrays.asList(1, 2),
    Arrays.asList(0, 2, 3),
    Arrays.asList(0, 1),
    Arrays.asList(1)
);

int[] distance = new int[N];

bfs(0, graph, distance);

System.out.println(Arrays.toString(distance)); // prints [0, 1, 1, 2]

Let's solve the following problem with the BFS:

Multi-source BFS

We can have BFS with multiple starting nodes: just add all of them to the queue in the beginning. As a result, we will get distance for each node to the closest of the starting nodes.

Let's try to solve the following problem:

Practice problems

Here are some more good problems to practice: