Course contentsShow
← Mathematics
Lesson 2673 of 3,12153. Graph TheoryFree lesson

Finding Spanning Trees: Depth-First Search

Use depth-first search (DFS) to systematically construct a spanning tree from any connected graph.

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

  1. Start at any vertex v and mark it visited
  2. Explore an unvisited neighbor u of v
  3. Add the edge (v, u) to your spanning tree
  4. Recurse: treat u as the new starting point and repeat
  5. Backtrack when a vertex has no unvisited neighbors
  6. 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.