Depth-first search, components and timestamps

Depth-first search (DFS) follows one path as far as it can and backs up only when the current vertex has no unvisited neighbour left. Written recursively it is a few lines: mark the vertex, then search from each unmarked neighbour. Like breadth-first search it visits every vertex and edge once, in O(V + E), but in a different order, and that order carries information. Starting a new search from every vertex no earlier search reached counts the connected components of an undirected graph. A clock that ticks when a vertex is discovered and again when it is finished gives every vertex two timestamps, and those times sort every edge into one of four kinds, one of which reveals cycles. On deep graphs the recursion can exceed the language’s call stack, so the explicit-stack version matters as much as the recursive one.

Going deep, then backing up

The trace below runs a recursive DFS from vertex 0 of a small directed graph. Each line is indented by the depth of the recursion, and the clock ticks once at each discovery and once at each finish:

# Recursive depth-first search on a small directed graph, with a clock that ticks once when a vertex is discovered and
# once when it is finished. Each line is indented by the depth of the recursion, so the printout is the DFS tree.
adj = {0: [1, 4, 3], 1: [2], 2: [0, 3], 3: [], 4: [3, 5], 5: [6], 6: [4]}

clock = 0
discovered = {}
finished = {}


def dfs(u, depth):
    global clock
    clock += 1
    discovered[u] = clock
    print(f"{'  ' * depth}discover {u} at {clock}")
    for v in adj[u]:
        if v not in discovered:
            dfs(v, depth + 1)
        else:
            state = "still open" if v not in finished else "already finished"
            print(f"{'  ' * (depth + 1)}{u} -> {v}: {v} is {state}")
    clock += 1
    finished[u] = clock
    print(f"{'  ' * depth}finish {u} at {clock}")


for s in adj:  # start again from every vertex not yet discovered (here one start is enough)
    if s not in discovered:
        dfs(s, 0)

print()
print("vertex  discovered  finished")
for u in sorted(adj):
    print(f"{u:>6}  {discovered[u]:>10}  {finished[u]:>8}")

discover 0 at 1
  discover 1 at 2
    discover 2 at 3
      2 -> 0: 0 is still open
      discover 3 at 4
      finish 3 at 5
    finish 2 at 6
  finish 1 at 7
  discover 4 at 8
    4 -> 3: 3 is already finished
    discover 5 at 9
      discover 6 at 10
        6 -> 4: 4 is still open
      finish 6 at 11
    finish 5 at 12
  finish 4 at 13
  0 -> 3: 3 is already finished
finish 0 at 14

vertex  discovered  finished
     0           1        14
     1           2         7
     2           3         6
     3           4         5
     4           8        13
     5           9        12
     6          10        11

The search went 0, 1, 2, 3 before it backed up, then took 0’s next neighbour, 4, and went down 4, 5, 6. Depth-first search keeps the current path on the call stack, and that path is what it backs up along. Every vertex gets its two timestamps, and between the two the search explores everything reachable from it that is still unvisited. The edges it follows to undiscovered vertices form the DFS tree; with several starts they form a forest. DFS sorts every edge into one of four kinds, named by what it finds at the far end of the edge:

• A tree edge leads to a vertex not yet discovered, and DFS follows it.
• A back edge leads to a vertex that is still open, an ancestor on the current path, as 2 → 0 does.
• A forward edge leads to a descendant that is already finished, as 0 → 3 does.
• A cross edge leads to a vertex finished before the current one was discovered, as 4 → 3 does.

A back edge closes a directed cycle with the tree path below its target, which is how DFS finds cycles in the lesson that follows.

Counting components

In an undirected graph, one search from a vertex marks exactly that vertex’s connected component. So loop over all vertices and start a new search from each one that is still unmarked: the number of starts is the number of components. On a grid the same idea is called flood fill. This map of land and water uses a list as an explicit stack instead of recursion:

# Connected components of a made-up map: # is land, . is water, and land cells that touch up, down, left or right
# belong to one island. Each search starts from a land cell no earlier search reached, and uses an explicit stack
# instead of recursion, so a very large island cannot exceed Python's recursion limit.
sea = [
    "##....#####.........",
    "##.....###.....##...",
    "......##.......##...",
    ".#.................#",
    ".###....######.....#",
    "..#.....#....#..####",
    "........######..#..#",
    "##..............####",
]
rows, cols = len(sea), len(sea[0])
label = [[None] * cols for _ in range(rows)]
sizes = []
for r0 in range(rows):
    for c0 in range(cols):
        if sea[r0][c0] != "#" or label[r0][c0] is not None:
            continue
        island = len(sizes)
        label[r0][c0] = island
        stack = [(r0, c0)]
        size = 0
        while stack:
            r, c = stack.pop()
            size += 1
            for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
                if 0 <= nr < rows and 0 <= nc < cols and sea[nr][nc] == "#" and label[nr][nc] is None:
                    label[nr][nc] = island
                    stack.append((nr, nc))
        sizes.append(size)

letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for r in range(rows):
    print("".join("." if label[r][c] is None else letters[label[r][c]] for c in range(cols)))
print()
print(f"{len(sizes)} islands, sizes", ", ".join(f"{letters[i]} {s}" for i, s in enumerate(sizes)))
print(f"{sum(sizes)} land cells in all; the largest island has {max(sizes)}")

AA....BBBBB.........
AA.....BBB.....CC...
......BB.......CC...
.D.................E
.DDD....FFFFFF.....E
..D.....F....F..EEEE
........FFFFFF..E..E
GG..............EEEE

7 islands, sizes A 4, B 10, C 4, D 5, E 12, F 14, G 2
51 land cells in all; the largest island has 14

Each letter is one component. Island F is a ring around a lake and island E has a hole, and neither confuses the search, because it only follows land cells that touch.

Recursion or an explicit stack

Each recursive call waits for the next one, so the recursion is as deep as the longest path the search walks down, up to V. CPython stops at sys.getrecursionlimit(), 1,000 by default, so a recursive DFS fails on a path of a few thousand vertices. A list used as a stack lives on the heap and avoids that. The simple version, which pops a vertex and pushes all its unmarked neighbours, finds the same components but visits vertices in a different order from the recursive one, so it gives different timestamps.

Exercise and self-check

Count the connected components of graphs with up to 200,000 vertices, including one path through all of them.

def count_components(n, edges):
    """The number of connected components of an undirected graph on vertices 0..n-1."""
    raise NotImplementedError("write count_components")

import random

from components import count_components


def slow_count(n, edges):
    """merge labels along the edges until nothing changes"""
    label = list(range(n))
    changed = True
    while changed:
        changed = False
        for u, v in edges:
            low = min(label[u], label[v])
            if label[u] != low or label[v] != low:
                label[u] = label[v] = low
                changed = True
    return len(set(label))


def test_small_graphs():
    """the lesson's eight-vertex graph has three components; a triangle has one"""
    assert count_components(8, [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (5, 6)]) == 3
    assert count_components(3, [(0, 1), (1, 2), (2, 0)]) == 1


def test_no_edges():
    """every vertex of a graph without edges is a component of its own"""
    assert count_components(5, []) == 5
    assert count_components(1, []) == 1


def test_loops_and_repeats():
    """a loop and a repeated edge change nothing"""
    assert count_components(4, [(0, 0), (1, 2), (2, 1), (1, 2)]) == 3


def test_random_graphs():
    """on 300 random graphs, matches a slow method that merges labels"""
    rng = random.Random(3)
    for _ in range(300):
        n = rng.randint(1, 30)
        edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 40))]
        assert count_components(n, edges) == slow_count(n, edges), (n, edges)


def test_long_path():
    """one path through 200,000 vertices, given in shuffled order: one component"""
    n = 200_000
    rng = random.Random(8)
    order = list(range(n))
    rng.shuffle(order)
    edges = [(order[i], order[i + 1]) for i in range(n - 1)]
    rng.shuffle(edges)
    assert count_components(n, edges) == 1
    assert count_components(n, edges[1:]) == 2

/** The number of connected components of an undirected graph on vertices 0..n-1. */
export function countComponents(n, edges) {
  throw new Error('write countComponents');
}

import { test, assert } from 'mysmartcopilot:test';
import { countComponents } from './components.mjs';

function slowCount(n, edges) {
  const label = Array.from({ length: n }, (_, i) => i);
  let changed = true;
  while (changed) {
    changed = false;
    for (const [u, v] of edges) {
      const low = Math.min(label[u], label[v]);
      if (label[u] !== low || label[v] !== low) {
        label[u] = label[v] = low;
        changed = true;
      }
    }
  }
  return new Set(label).size;
}

test("the lesson's eight-vertex graph has three components; a triangle has one", () => {
  assert.equal(countComponents(8, [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4], [5, 6]]), 3);
  assert.equal(countComponents(3, [[0, 1], [1, 2], [2, 0]]), 1);
});

test('every vertex of a graph without edges is a component of its own', () => {
  assert.equal(countComponents(5, []), 5);
  assert.equal(countComponents(1, []), 1);
});

test('a loop and a repeated edge change nothing', () => {
  assert.equal(countComponents(4, [[0, 0], [1, 2], [2, 1], [1, 2]]), 3);
});

test('on 300 random graphs, matches a slow method that merges labels', () => {
  let seed = 3;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  for (let k = 0; k < 300; k++) {
    const n = 1 + Math.floor(random() * 30);
    const edges = Array.from({ length: Math.floor(random() * 41) }, () => [Math.floor(random() * n), Math.floor(random() * n)]);
    assert.equal(countComponents(n, edges), slowCount(n, edges), JSON.stringify([n, edges]));
  }
});

test('one path through 200,000 vertices, given in shuffled order: one component', () => {
  const n = 200000;
  let seed = 8;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const shuffle = (a) => {
    for (let i = a.length - 1; i > 0; i--) {
      const j = Math.floor(random() * (i + 1));
      [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
  };
  const order = shuffle(Array.from({ length: n }, (_, i) => i));
  const edges = shuffle(Array.from({ length: n - 1 }, (_, i) => [order[i], order[i + 1]]));
  assert.equal(countComponents(n, edges), 1);
  assert.equal(countComponents(n, edges.slice(1)), 2);
});

Timestamps in depth: nesting, edge types and cycles, proved and checked Pro: opens with a Pro, Premium or Ultimate pass

Deep graphs: an explicit stack that keeps the recursive order Pro: opens with a Pro, Premium or Ultimate pass

Components in five languages, and how deep each one can recurse Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• DFS goes deep first and backs up, in O(V + E); recursively it is a few lines, iteratively it needs a stack.
• Starting a search from every unmarked vertex counts connected components: one start per component.
• Discovery and finish times nest along the DFS tree, and they sort edges into tree, back, forward and cross edges; a back edge in a directed graph means a cycle.
• Recursion depth can reach V, so use an explicit stack for graphs from input.