4.3.1.1 - Breadth-first and depth-first graph traversal (Java)

Breadth-first search and queues

Breadth-first search explores the start vertex's neighbours before vertices further away, using a queue to keep discovered vertices in first-in, first-out order.

The example is an undirected graph. A vertex's adjacency list is examined in the listed order: A: B, C; B: A, D; C: A, D, E; D: B, C, F; E: C, F; F: D, E. Mark a vertex discovered when adding it, rather than when removing it, so two parents cannot queue it twice. Starting at A gives the following state; queue front is at the left.

[DIAGRAM: asset_slug: traversal_graph; description: Undirected graph A–F with exactly the adjacency relationships used in the breadth-first and depth-first traces.]

With indices A=0 through F=5, the method below returns the processing order. These methods belong inside a class; import java.util.*; supplies the collection classes. The start index and every neighbour index are guaranteed valid.

static List<Integer> bfs(int[][] neighbours, int start) {
    boolean[] discovered = new boolean[neighbours.length];
    Deque<Integer> queue = new ArrayDeque<>();
    List<Integer> order = new ArrayList<>();
    discovered[start] = true;
    queue.addLast(start);
    while (!queue.isEmpty()) {
        int u = queue.removeFirst();
        order.add(u);
        for (int v : neighbours[u]) {
            if (!discovered[v]) {
                discovered[v] = true;
                queue.addLast(v);
            }
        }
    }
    return order;
}

An isolated start still produces a one-element list. A single search visits only the component reachable from its start, not disconnected vertices elsewhere.