Elijah's Notes

Depth First Search Algorithm and Tree Properties

3 min read

Purpose

Running DFS on a graph produces a DFS tree (a depth-first spanning tree of the starting vertex’s component). The tree contains every vertex DFS reaches, and its edges are a subset of the graph’s edges. This note gives the implementations and proves the one structural property that makes DFS trees useful.

Core idea

Unlike the BFS tree, a DFS tree has no minimum-depth guarantee, and its levels say nothing about distance. What it does guarantee: no edge of the graph connects two different subtrees. Every non-tree edge climbs between a vertex and one of its ancestors. That is why DFS finds cycles: any non-tree edge closes a cycle through the tree path between its endpoints.

Lemma: Let be a DFS tree of graph . For every edge with , one of or is an ancestor of the other in .

Proof: Without loss of generality, assume is discovered first. When is called, is still undiscovered. The call does not return until every neighbor of has been discovered, since it visits each neighbor and recurses on the undiscovered ones. So is discovered during , which places somewhere in the subtree rooted at , making an ancestor of .

A DFS from vertex 1 that visits 1, 2, 3, 4, backtracks, then visits 5 and 6. Solid edges are tree edges, dashed edges are the non-tree edges of :

flowchart TD
    v1((1)) --- v2((2))
    v2 --- v3((3))
    v3 --- v4((4))
    v1 --- v5((5))
    v5 --- v6((6))
    v4 -.- v2
    v6 -.- v1

    style v1 fill:#e3f2fd,stroke:#1565c0

Both dashed edges climb from a vertex to one of its ancestors. No edge joins the subtree of 2 to the subtree of 5, and the lemma says no such edge can exist.

Where non-tree edges can go

BFS and DFS trees constrain non-tree edges in opposite directions. In a BFS tree, a non-tree edge stays within one level but can join unrelated subtrees. In a DFS tree, a non-tree edge can span many levels but always joins a vertex to an ancestor. Each traversal forbids exactly the edges the other allows.

Implementation

def dfs_recursive(G, src, vis=None, f=print):
    if vis is None:
        vis = set()
    if src in vis:
        return
    vis.add(src)
    f(src)
    for v in G[src]:
        dfs_recursive(G, v, vis, f)
 
def dfs_iterative(G, src, f=print):
    vis = set()
    stack = [src]
    while stack:
        curr = stack.pop()
        if curr in vis:
            continue
        vis.add(curr)
        f(curr)
        for v in G[curr]:
            stack.append(v)

Recursion depth

dfs_recursive adds a stack frame for every vertex on the current path, so a long path graph exceeds Python’s default recursion limit of 1000 and raises RecursionError. Use dfs_iterative when the input can be deep.

Properties of DFS Spanning Trees

DFS visits every vertex in the starting vertex’s connected component, so it finds connected components just like BFS does.

The ancestor property is what sets DFS apart. Since every non-tree edge joins a vertex to an ancestor or descendant, DFS gives a clean way to detect cycles, and it underlies algorithms on directed acyclic graphs like topological sorting.

Graph View