Finding Spanning Trees: Depth-First Search
You'll learn: How to use depth-first search (DFS) to systematically build a spanning tree from any connected graph.
Core Idea
A spanning tree touches every vertex of a connected graph using exactly n − 1 edges (where n is the number of vertices), with no cycles. Depth-first search is a natural algorithm for constructing one: it explores as far as possible along each branch before backtracking, adding edges as it discovers new vertices.
Think of exploring a maze by always going forward until you hit a dead end, then backing up to try the next unexplored passage. The path you took to reach each room forms a tree.
How DFS Constructs a Spanning Tree
- Start at any vertex v and mark it visited
- Explore an unvisited neighbor u of v
- Add the edge (v, u) to your spanning tree
- Recurse: treat u as the new starting point and repeat
- Backtrack when a vertex has no unvisited neighbors
- Continue until all vertices are visited
The edges you add during discovery form the spanning tree. Edges leading to already-visited vertices are ignored—they would create cycles.
Why This Works
DFS guarantees you visit every vertex exactly once in a connected graph. Since you add an edge only when discovering a new vertex, you accumulate exactly n − 1 edges without forming cycles. The result satisfies the definition of a spanning tree.
The specific tree you get depends on your starting vertex and the order you explore neighbors, but DFS will always produce some valid spanning tree.
Key Takeaway: Depth-first search naturally builds a spanning tree by exploring deeply, marking vertices as visited, and recording discovery edges—giving you a systematic, cycle-free way to connect all vertices.