Transitive Closure

Transitive Closure asks a deceptively simple question about a directed graph: for every pair of vertices, can you get from one to the other — directly or by following a chain of edges? The answer is a full reachability table, and the trick to building it is one of the most reusable patterns in graph algorithms.

The slow way first

The obvious idea: run a separate graph search (BFS or DFS) starting from every vertex, marking everything it can reach. That works and is O(V·(V + E)), which is fine for sparse graphs but fiddly to code and easy to get wrong with cycles.

The question to ask: is there a way to grow reachability without restarting a search from scratch each time? What if, instead of exploring paths, we let paths assemble themselves out of shorter known paths?

The idea: route through a middle vertex

Walk over every possible intermediate vertex k. For each pair (i, j), ask: can i reach k, and can k reach j? If both are already known, then i can reach j by passing through k. In one line:

reach[i][j] |= reach[i][k] && reach[k][j]

By looping k on the outside, every newly discovered link becomes available for the next k, so chains of any length get stitched together. This is Floyd–Warshall, specialized to booleans.

The key insight: k must be the outermost loop. That ordering guarantees that when we use reach[i][k], every path into k discovered so far is already recorded.

Walk through it

Step through the animation. The grid is the reachability matrix — rows are "from", columns are "to". The pointer k slides across, and for each k we highlight its row and column (the operands we read). When both reach[i][k] and reach[k][j] are 1, the target cell reach[i][j] flips on. Watch reach[0][2] light up when k = 1: that is 0 → 1 → 2 being discovered.

Pseudocode

n = number of vertices
for each intermediate vertex k in 0..n-1:
    for each source i in 0..n-1:
        for each target j in 0..n-1:
            if reach[i][k] and reach[k][j]:
                reach[i][j] = 1          # i can reach j via k
return reach                              # full transitive closure

The Python solution

def transitive_closure(reach):
    n = len(reach)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

• reach is the boolean matrix: reach[i][j] is whether i can reach j. The diagonal is usually 1 (a vertex reaches itself).
• The k loop is outermost — that is the whole correctness argument. Each k lets us extend paths through that vertex.
• i and j scan every ordered pair of vertices.
• The update reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]) keeps any existing link and adds the new "via k" link.
• After all k, every cell answers the reachability question exactly.

Complexity

The matrix approach is O(V³) time and O(V²) space (the matrix itself). For dense graphs it is often the simplest and fastest choice; its tight triple loop also vectorizes well with bitsets.

When this pattern shows up

Practice