Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

Basic Implementation

Basic.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Basic {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> adj = new LinkedHashMap<>();
        adj.put(1, List.of(2, 3));
        adj.put(2, List.of(1, 4));
        adj.put(3, List.of(1, 4));
        adj.put(4, List.of(2, 3, 5));
        adj.put(5, List.of(4, 6));
        adj.put(6, List.of(5));

        int src = 1;
        int dst = 6;
        Map<Integer, Integer> dist = new LinkedHashMap<>();
        Map<Integer, Integer> parent = new LinkedHashMap<>();
        dist.put(src, 0);
        parent.put(src, null);
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(src);
        while (!queue.isEmpty()) {
            int v = queue.pollFirst();
            for (int nb : adj.get(v)) {
                if (!dist.containsKey(nb)) {
                    dist.put(nb, dist.get(v) + 1);
                    parent.put(nb, v);
                    queue.addLast(nb);
                }
            }
        }

        List<Integer> path = new ArrayList<>();
        Integer node = dst;
        while (node != null) {
            path.add(node);
            node = parent.get(node);
        }
        Collections.reverse(path);
        System.out.println(path);
        System.out.println(dist.get(dst));
    }
}

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Java: a dist map doubles as the visited check (a vertex is discovered once dist contains it), parent records the predecessor, and an ArrayDeque is the FIFO queue.
The replay shows dist, parent, and the queue filling in, then the reconstructed path, matching the lesson spec.

layers equal distance BFS order equals distance in an unweighted graph.