templates · Graph traversal

BFS shortest path (unweighted graph)

  • "Fewest steps", "minimum moves" or "shortest transformation" and every step costs the same
  • States connect to each other: words one letter apart, board squares, lock combinations
  • You need the distance to every node, or one actual shortest route

BFS shortest path (unweighted)Graph DFS / BFS traversal

the one rule

The invariant

The queue holds nodes in order of distance, so the first time a node is seen, its distance is final.

write it from memory

The template

distance to every node

javajava.util.*
/** Fewest edges from src to every node of an undirected graph; -1 = unreachable. */static int[] distances(int n, int[][] edges, int src) {    List<List<Integer>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());    for (int[] e : edges) {                           // build the graph once        adj.get(e[0]).add(e[1]);        adj.get(e[1]).add(e[0]);    }    int[] dist = new int[n];    Arrays.fill(dist, -1);                            // -1 = not seen yet    Deque<Integer> queue = new ArrayDeque<>();    dist[src] = 0;                                    // the start    queue.offer(src);    while (!queue.isEmpty()) {        int u = queue.poll();        for (int v : adj.get(u)) {                    // neighbours of u            if (dist[v] != -1) continue;              // already queued: skip            dist[v] = dist[u] + 1;                    // mark when you PUSH, not when you pop            queue.offer(v);        }    }    return dist;}

dist doubles as the visited mark. -1 means "not seen yet".

fill in the blanks — only these lines change per problem

  1. line 5How the graph is given. Edges here; for word ladder the "neighbours" are words one letter apart, made on the fly.
  2. line 12Where the search starts. One source here; many sources means multi-source BFS.
  3. line 16How to list the next states, e.g. a ladder or snake on the board, or eight knight moves.

rebuild one shortest path

javajava.util.*
/** One shortest path src → target as a list of nodes; empty if target cannot be reached. */static List<Integer> shortestPath(int n, int[][] edges, int src, int target) {    List<List<Integer>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());    for (int[] e : edges) {        adj.get(e[0]).add(e[1]);        adj.get(e[1]).add(e[0]);    }    int[] parent = new int[n];    Arrays.fill(parent, -2);                          // -2 = not seen; the start gets -1    Deque<Integer> queue = new ArrayDeque<>();    parent[src] = -1;    queue.offer(src);    while (!queue.isEmpty()) {        int u = queue.poll();        if (u == target) break;                       // first time we pop it = shortest        for (int v : adj.get(u)) {            if (parent[v] != -2) continue;            parent[v] = u;                            // remember who found v            queue.offer(v);        }    }    LinkedList<Integer> path = new LinkedList<>();    if (parent[target] == -2) return path;            // never reached    for (int v = target; v != -1; v = parent[v]) path.addFirst(v); // walk back to the start    return path;}

Store who discovered each node. Then walk parent back from the target and reverse.

fill in the blanks — only these lines change per problem

  1. line 16When to stop early: the target is popped, or a goal test like word.equals(end).
  2. line 24What to return when the target is never reached: an empty list, -1 or 0, as asked.

complexity

What it costs

time O(V + E)
Each node is queued at most once, and each edge is looked at once from each end.
space O(V + E)
The adjacency list holds every edge; dist, parent and the queue hold at most V entries.

watch out

Common bugs

  • Marking a node visited when you pop it instead of when you push it. The same node enters the queue many times and it can time out.
  • Using BFS when steps have different costs. Then the first arrival is not the cheapest; use Dijkstra.
  • Forgetting Arrays.fill(dist, -1). Java's default 0 then makes unreachable nodes look like the start, and they are never visited.

use it

Practise it on

learn it properly