Depth-first search applications

Depth-first search does more than visit every vertex. The order in which it discovers and finishes vertices reveals the structure of a directed graph: whether it has cycles, how its vertices can be ordered so that every edge points forward, and how it breaks into groups of mutually reachable vertices. This lesson develops three linear-time algorithms built on DFS: cycle detection, topological sorting and strongly connected components. They power build systems, spreadsheet recalculation, package managers, deadlock detection and the analysis of web and social networks.

Classifying edges

When DFS runs on a directed graph, every edge \((u, v)\) falls into one of four classes, determined by the timestamps from lesson 7. A tree edge leads to an undiscovered vertex and becomes part of the DFS forest. A back edge leads from \(u\) to one of its ancestors, a vertex that has been discovered but not yet finished. A forward edge leads to a descendant that is already finished. A cross edge leads to a vertex that is finished and is neither an ancestor nor a descendant, in another branch or another tree of the forest.

A three-colour bookkeeping scheme makes the classification easy to implement. Each vertex is white before discovery, grey while it is on the recursion stack and black once finished. An edge to a white vertex is a tree edge, an edge to a grey vertex is a back edge, and an edge to a black vertex is a forward or cross edge, distinguished by comparing discovery times. In an undirected graph only tree and back edges occur, because every edge is explored first from whichever endpoint is discovered first.

Cycle detection

A directed graph has a cycle if and only if DFS finds a back edge. One direction is immediate: a back edge \((u, v)\) together with the tree path from \(v\) down to \(u\) forms a cycle. For the other direction, suppose the graph has a cycle and let \(v\) be the first vertex of the cycle that DFS discovers. At that moment every other vertex of the cycle is white and reachable from \(v\), so by the white-path theorem each becomes a descendant of \(v\). In particular, the vertex \(u\) just before \(v\) on the cycle is a descendant, and the edge \((u, v)\) is examined while \(v\) is still grey, so it is a back edge. Cycle detection therefore runs in \(\Theta(n + m)\).

import sys
sys.setrecursionlimit(10000)
NEW, ACTIVE, DONE = 0, 1, 2

def classify(adj):
    state = {u: NEW for u in adj}
    d, time, kinds = {}, [0], []
    def visit(u):
        state[u] = ACTIVE; time[0] += 1; d[u] = time[0]
        for v in adj[u]:
            if state[v] == NEW:
                kinds.append((u, v, 'tree')); visit(v)
            elif state[v] == ACTIVE:
                kinds.append((u, v, 'back'))
            elif d[u] < d[v]:
                kinds.append((u, v, 'forward'))
            else:
                kinds.append((u, v, 'cross'))
        state[u] = DONE
    for u in adj:
        if state[u] == NEW:
            visit(u)
    return kinds

g = {'a': ['b', 'c'], 'b': ['d'], 'c': ['d'], 'd': ['a', 'e'], 'e': [], 'f': ['e', 'c']}
for u, v, k in classify(g):
    print(f'{u} -> {v}: {k}')
print('has cycle:', any(k == 'back' for _, _, k in classify(g)))

a -> b: tree
b -> d: tree
d -> a: back
d -> e: tree
a -> c: tree
c -> d: cross
f -> e: cross
f -> c: cross
has cycle: True

The back edge from d to a reveals the cycle a, b, d, a. The edge from c to d is a cross edge, because d was finished in the branch through b before the search reached c. The edges from f lead into the tree that was already explored, so they are cross edges too. The code names the three states NEW, ACTIVE and DONE for white, grey and black; any three distinct values would work.

Directed acyclic graphs and topological order

A directed acyclic graph, or DAG, has no directed cycles. DAGs model dependencies: course prerequisites, tasks that must precede other tasks, modules a program imports, cells a spreadsheet formula depends on. A topological order is a listing of the vertices in which every edge \((u, v)\) has \(u\) before \(v\). CMPUT-272 lesson 9 showed that a partial order can always be extended to a total order; here we compute one in linear time. A directed graph has a topological order if and only if it is acyclic: an order cannot exist if there is a cycle, because some edge of the cycle would have to point backward.

The DFS method is short and elegant: run DFS and list the vertices in decreasing order of finish time. To see why this works, consider any edge \((u, v)\) in a DAG. When it is examined, \(v\) cannot be grey, since that would make it a back edge and the graph would have a cycle. If \(v\) is white, it becomes a descendant of \(u\) and finishes before \(u\). If \(v\) is black, it has already finished. Either way \(f[v] < f[u]\), so \(u\) appears before \(v\) when we sort by decreasing finish time. In practice we push each vertex onto a list as it finishes and reverse the list at the end, so no sorting is needed.

A second method, Kahn's algorithm, works from the other end. Compute each vertex's in-degree, the number of edges entering it. Put every vertex with in-degree 0 in a queue; these have no unmet prerequisites. Repeatedly remove a vertex from the queue, output it, and decrease the in-degree of each of its out-neighbours, enqueuing any whose in-degree drops to 0. If the algorithm outputs every vertex, the order is topological; if vertices remain with positive in-degree, they lie on or behind a cycle. Kahn's algorithm also runs in \(\Theta(n + m)\) and is popular in build tools because it reports exactly which items are blocked.

from collections import deque

prereq = {                         # edge u -> v means u must come before v
    'CMPUT-174': ['CMPUT-201', 'CMPUT-272'],
    'CMPUT-201': ['CMPUT-204', 'CMPUT-229', 'CMPUT-291'],
    'CMPUT-272': ['CMPUT-204'],
    'CMPUT-204': ['CMPUT-304', 'CMPUT-366'],
    'CMPUT-229': ['CMPUT-379'],
    'CMPUT-291': [], 'CMPUT-304': [], 'CMPUT-366': [], 'CMPUT-379': [],
}

def topo_dfs(adj):
    seen, out = set(), []
    def visit(u):
        seen.add(u)
        for v in adj[u]:
            if v not in seen:
                visit(v)
        out.append(u)                  # u finishes after all its descendants
    for u in adj:
        if u not in seen:
            visit(u)
    return out[::-1]

def topo_kahn(adj):
    indeg = {u: 0 for u in adj}
    for u in adj:
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in adj if indeg[u] == 0)
    out = []
    while q:
        u = q.popleft(); out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    blocked = [u for u in adj if indeg[u] > 0]
    return out, blocked

def respects(order, adj):
    pos = {u: i for i, u in enumerate(order)}
    return all(pos[u] < pos[v] for u in adj for v in adj[u])

a = topo_dfs(prereq); b, blocked = topo_kahn(prereq)
print('DFS :', ' '.join(c[-3:] for c in a), respects(a, prereq))
print('Kahn:', ' '.join(c[-3:] for c in b), respects(b, prereq), 'blocked:', blocked)
prereq['CMPUT-304'] = ['CMPUT-272']    # introduce a cycle 272 -> 204 -> 304 -> 272
print('with a cycle, blocked:', topo_kahn(prereq)[1])

DFS : 174 272 201 291 229 379 204 366 304 True
Kahn: 174 201 272 229 291 204 379 304 366 True blocked: []
with a cycle, blocked: ['CMPUT-272', 'CMPUT-204', 'CMPUT-304', 'CMPUT-366']

The two methods produce different but equally valid orders, since a DAG usually has many topological orders. When an edge creates a cycle, Kahn's algorithm cannot release CMPUT-272, CMPUT-204 or CMPUT-304, nor CMPUT-366, which waits on one of them, and reports all four as blocked.

Strongly connected components

In a directed graph, vertices \(u\) and \(v\) are strongly connected if each is reachable from the other. This relation is an equivalence relation, so it partitions the vertices into strongly connected components, or SCCs. Inside an SCC, every vertex can reach every other; between SCCs, edges go only one way. Shrinking each SCC to a single vertex gives the component graph, or condensation, which is always a DAG. SCCs identify groups of web pages that link to each other, mutually recursive functions in a program, and sets of processes that may deadlock.

Kosaraju's algorithm finds all SCCs with two depth-first searches. First, run DFS on \(G\) and record the vertices in order of finish time. Second, form the transpose graph \(G^T\), which has every edge reversed, and run DFS on it, taking start vertices in decreasing order of first-pass finish time. Each tree of the second search is exactly one SCC. The intuition is that the vertex with the latest finish time lies in a source component of the condensation; in the reversed graph, that component is a sink, so DFS from it cannot escape and collects exactly that component. Removing it and repeating peels off components one at a time. The total cost is \(\Theta(n + m)\). Tarjan's algorithm finds the same components in a single DFS using low-link values and is often faster in practice.

import sys
sys.setrecursionlimit(10000)

def kosaraju(adj):
    order, seen = [], set()
    def first(u):
        seen.add(u)
        for v in adj[u]:
            if v not in seen:
                first(v)
        order.append(u)
    for u in adj:
        if u not in seen:
            first(u)
    radj = {u: [] for u in adj}               # transpose graph
    for u in adj:
        for v in adj[u]:
            radj[v].append(u)
    comp, comps = {}, []
    def second(u, label):
        comp[u] = label; comps[-1].append(u)
        for v in radj[u]:
            if v not in comp:
                second(v, label)
    for u in reversed(order):                 # decreasing finish time
        if u not in comp:
            comps.append([])
            second(u, len(comps) - 1)
    return comps

g = {1: [2], 2: [3, 4], 3: [1], 4: [5], 5: [6], 6: [4, 7], 7: [], 8: [7, 8]}
for c in kosaraju(g):
    print(sorted(c))

[8]
[1, 2, 3]
[4, 5, 6]
[7]

The output lists four components in an order that is itself a topological order of the condensation. Vertex 8, with its self-loop, forms a component of its own that reaches {7}. The component {1, 2, 3} can reach {4, 5, 6}, which can reach {7}, and {7} comes last because it reaches nothing. Any directed graph is thus a DAG of strongly connected pieces, which is often the most useful way to understand it.