Graphs

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.

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

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
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));
    }
}

  1. dist ← {1: 0}

    22Map<Integer, Integer> parent = new LinkedHashMap<>();23dist.put(src, 0);24parent.put(src, null);
    values this step{1: 0}dist

  2. parent ← {1: null}

    23dist.put(src, 0);24parent.put(src, null);25Deque<Integer> queue = new ArrayDeque<>();
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    27while (!queue.isEmpty()) {28    int v = queue.pollFirst();29    for (int nb : adj.get(v)) {
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    27while (!queue.isEmpty()) {28    int v = queue.pollFirst();29    for (int nb : adj.get(v)) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    27while (!queue.isEmpty()) {28    int v = queue.pollFirst();29    for (int nb : adj.get(v)) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    27while (!queue.isEmpty()) {28    int v = queue.pollFirst();29    for (int nb : adj.get(v)) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    27while (!queue.isEmpty()) {28    int v = queue.pollFirst();29    for (int nb : adj.get(v)) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    27while (!queue.isEmpty()) {28    int v = queue.pollFirst();29    for (int nb : adj.get(v)) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    43}44Collections.reverse(path);45System.out.println(path);
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← [1, 2, 4, 5, 6]

    44Collections.reverse(path);45System.out.println(path);46System.out.println(dist.get(dst));
    values this step[1, 2, 4, 5, 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    45    System.out.println(path);46    System.out.println(dist.get(dst));47}
    values this step4stdout4dist[6]

  12. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    45    System.out.println(path);46    System.out.println(dist.get(dst));47}
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

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. It also contrasts that unweighted result with a weighted graph where Dijkstra with a priority queue is required.