templates · Graph traversal

Graph DFS (recursive & iterative)

  • "How many groups / provinces / connected pieces?"
  • "Can I reach B from A?" or "visit everything once" (copy a graph, collect a group)
  • The order of visiting does not matter, only that every reachable node is seen

Graph DFS / BFS traversal

the one rule

The invariant

A node is marked seen before its neighbours are explored, so every node is visited exactly once.

write it from memory

The template

recursive: count components

javajava.util.*
/** Number of connected components in an undirected graph with nodes 0..n-1. */static int countComponents(int n, int[][] edges) {    List<List<Integer>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());    for (int[] e : edges) {                           // undirected: add both ways        adj.get(e[0]).add(e[1]);        adj.get(e[1]).add(e[0]);    }    boolean[] seen = new boolean[n];    int components = 0;    for (int start = 0; start < n; start++) {         // try every node: the graph may be split        if (seen[start]) continue;        components++;                                 // a new piece of the graph        dfs(start, adj, seen);    }    return components;} static void dfs(int u, List<List<Integer>> adj, boolean[] seen) {    seen[u] = true;                                   // mark on entry    for (int v : adj.get(u)) {        if (!seen[v]) dfs(v, adj, seen);              // go deep first    }}

The outer loop tries every node, because one DFS only covers one piece of the graph.

fill in the blanks — only these lines change per problem

  1. line 5How the graph arrives: an edge list, an adjacency matrix (Number of Provinces) or node objects (Clone Graph).
  2. line 13What you collect per piece: a count, the piece's size, or the list of its nodes (Accounts Merge).
  3. line 20The work at each node: copy it, add it to a group, or check a colour.

iterative: explicit stack

javajava.util.*
/** Every node reachable from src, in DFS order, with an explicit stack (no recursion limit). */static List<Integer> reachable(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) {        adj.get(e[0]).add(e[1]);        adj.get(e[1]).add(e[0]);    }    boolean[] seen = new boolean[n];    List<Integer> order = new ArrayList<>();    Deque<Integer> stack = new ArrayDeque<>();    stack.push(src);    while (!stack.isEmpty()) {        int u = stack.pop();        if (seen[u]) continue;                        // may be pushed twice; visit once        seen[u] = true;        order.add(u);                                 // visit u        for (int v : adj.get(u)) {            if (!seen[v]) stack.push(v);        }    }    return order;}

Use this when the graph can be a very long chain. An ArrayDeque never overflows the way the call stack can.

fill in the blanks — only these lines change per problem

  1. line 17What "visiting" means for this problem; same as the recursive version.

complexity

What it costs

time O(V + E)
Each node is entered once, and each edge is looked at once from each end.
space O(V + E)
The adjacency list holds every edge. The call stack can grow to V on a long chain; the explicit stack can hold up to about E entries, because a node may be pushed more than once before it is visited.

watch out

Common bugs

  • Starting DFS only from node 0. A disconnected graph has nodes you never reach.
  • Adding only one direction for an undirected edge, so some nodes look unreachable.
  • Marking seen too late (after the recursive calls), which can loop forever on a cycle.

use it

Practise it on

learn it properly