8.2 Breadth-First Search | Code Scholars Tutoring

How it works

BFS uses a queue and expands in layers, so the first time it reaches a vertex it has used the fewest edges. That is why it solves unweighted shortest paths.

Use BFS when the fewest steps matters and edges carry no weight.

Common error

Expecting BFS to handle weighted shortest paths. Layer order is not weight order.

Worked example

Example

Graph: A-B, A-C, B-D, C-D
Start A; neighbors processed alphabetically
Queue initially: A
Mark each vertex when enqueued

Breadth-first search visits vertices by increasing edge distance from the start in an unweighted graph. Marking at enqueue time prevents the same discovered vertex from being queued repeatedly.

Edges are A-B, A-C, B-D, and C-D. — Edges A-B, A-C, B-D, and C-D; visit order depends on traversal strategy and neighbor order.

Exercises

8.2.1 · Explain

Give BFS order and the edge distance from A to D for the displayed graph.

Show solution

The order is A, B, C, D under alphabetical neighbor processing. D has distance 2 from A.

8.2.2 · Write code

Implement BFS from A for the displayed graph, processing each adjacency list alphabetically. Mark vertices when enqueued.

Show solution

A queue preserves distance layers and a visited set prevents duplicate enqueues.

One valid solution

Map<String,List<String>> graph = Map.of(
    "A", List.of("B","C"), "B", List.of("A","D"),
    "C", List.of("A","D"), "D", List.of("B","C"));
Queue<String> queue = new ArrayDeque<String>();
Set<String> seen = new HashSet<String>();
queue.offer("A"); seen.add("A");
while (!queue.isEmpty()) {
    String node = queue.remove();
    System.out.print(node + " ");
    for (String next : graph.get(node))
        if (seen.add(next)) queue.offer(next);
}

Expected output

A B C D

Open Java compiler