Graph Algorithms contents

Depth-First Search

Explore a graph as deep as possible before backtracking; entry and exit times, edge classification, and how to avoid Python's recursion limit.

Beginner7 min readdfstraversalrecursionstacktimestamps

Read first: Graphs: Terminology and Representation, Recursion

Depth-first search (DFS) goes as deep as possible along a path before backtracking. Where BFS uses a queue and explores by distance, DFS uses a stack (explicitly or via recursion) and explores by following one branch to its end.

Its running time is $O(n + m)$ , and it is the basis of many algorithms: connected components, cycle detection, topological sorting, bridges, strongly connected components.

Algorithm

From vertex $v$ : mark it visited; for each neighbour $u$ that has not been visited, recursively run DFS from $u$ . When all neighbours are done, return.

python

def dfs_recursive(adj, s):
    visited = [False] * len(adj)
    order = []

    def go(v):
        visited[v] = True
        order.append(v)
        for u in adj[v]:
            if not visited[u]:
                go(u)

    go(s)
    return order

adj = [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
assert dfs_recursive(adj, 0) == [0, 1, 3, 2, 4]

Iterative DFS

Use an explicit stack. The simplest version pushes all neighbours; the visit order may differ from the recursive one, but it's a valid DFS order (each vertex is visited before the vertices discovered from it):

python

def dfs_iterative(adj, s):
    visited = [False] * len(adj)
    order = []
    stack = [s]
    while stack:
        v = stack.pop()
        if visited[v]:
            continue
        visited[v] = True
        order.append(v)
        for u in reversed(adj[v]):          # reversed: process neighbours in list order
            if not visited[u]:
                stack.append(u)
    return order

assert dfs_iterative(adj, 0) == dfs_recursive(adj, 0)

For algorithms that need the exit moment (post-order, timestamps, low-link values), keep an iterator index for each vertex on the stack, so the vertex stays on the stack until all its neighbours have been processed:

python

def dfs_times(adj, s):
    """Iterative DFS returning entry times, exit times and parents."""
    n = len(adj)
    tin, tout = [-1] * n, [-1] * n
    parent = [-1] * n
    next_i = [0] * n                          # next neighbour index to examine, per vertex
    timer = 0
    tin[s] = timer; timer += 1
    stack = [s]
    while stack:
        v = stack[-1]
        if next_i[v] < len(adj[v]):
            u = adj[v][next_i[v]]
            next_i[v] += 1
            if tin[u] == -1:
                parent[u] = v
                tin[u] = timer; timer += 1
                stack.append(u)
        else:
            tout[v] = timer; timer += 1
            stack.pop()
    return tin, tout, parent

tin, tout, parent = dfs_times(adj, 0)
assert (tin[0], tout[0]) == (0, 9)
assert parent == [-1, 0, 3, 1, 3]                 # vertex 2 is discovered from 3, not from 0

Entry and exit times

Record tin[v] when DFS enters $v$ and tout[v] when it leaves. They give constant-time tests about the DFS tree:

$u$ is an ancestor of $v$ exactly when $\text{tin}[u] \le \text{tin}[v]$ and $\text{tout}[v] \le \text{tout}[u]$ ;
sorting vertices by tout descending gives a topological order of a DAG.

python

def is_ancestor(u, v):
    return tin[u] <= tin[v] and tout[v] <= tout[u]

assert is_ancestor(0, 4) and is_ancestor(1, 3) and not is_ancestor(2, 3)

Classification of edges

In a directed graph, during a DFS every edge $v \to u$ is one of:

Kind	How to recognise it when examined
tree edge	$u$ is unvisited
back edge	$u$ is visited and still on the stack (an ancestor): closes a cycle
forward edge	$u$ is a visited descendant of $v$
cross edge	$u$ is visited, finished, and not a descendant

In an undirected graph only tree edges and back edges exist. A directed graph has a cycle if and only if DFS finds a back edge; see finding a cycle.

Applications

Connected components (article).
Topological sorting (article).
Cycle detection (article).
Bridges and articulation points (bridges, articulation points).
Strongly connected components (article).
Subtree computations on trees: sizes, depths, sums, using the order in which DFS finishes vertices.

python

def subtree_sizes(adj, root):
    """Size of the subtree of every vertex of a tree, computed without recursion."""
    n = len(adj)
    parent = [-1] * n
    order = []
    stack = [root]
    while stack:
        v = stack.pop()
        order.append(v)
        for u in adj[v]:
            if u != parent[v]:
                parent[u] = v
                stack.append(u)
    size = [1] * n
    for v in reversed(order):                # children come after parents in `order`
        if parent[v] != -1:
            size[parent[v]] += size[v]
    return size

tree = [[1, 2], [0, 3, 4], [0], [1], [1]]
assert subtree_sizes(tree, 0) == [5, 3, 1, 1, 1]

The pattern "collect a pre-order, then process it in reverse" replaces most recursive tree DP in Python.

BFS or DFS?

Need	Use
shortest path (unweighted)	BFS
any path, components, cycle, ordering, ancestors	DFS
the state space is very deep and narrow	DFS (memory)

Algorithm

Iterative DFS

Entry and exit times

Classification of edges

Applications

BFS or DFS?

Practice problems