Finding Spanning Trees: Breadth-First Search
You'll learn how to use breadth-first search (BFS) to construct spanning trees that reveal the level structure of a graph.
What Is BFS?
Breadth-first search is a graph traversal algorithm that explores vertices in layers, like ripples spreading out from a stone dropped in water. Starting from a source vertex, BFS first visits all vertices one edge away, then all vertices two edges away, and so on.
Building a Spanning Tree with BFS
When you run BFS on a connected graph, you naturally build a spanning tree:
- Start at any vertex v (the root)
- Explore all vertices adjacent to v (level 1)
- Mark edges used to reach new vertices—these become tree edges
- Continue layer by layer, only adding edges that reach previously unvisited vertices
- Ignore edges leading to already-visited vertices (these would create cycles)
The resulting tree is called a BFS tree or breadth-first spanning tree.
Level Structure
BFS naturally organizes vertices into levels:
- Level 0: the starting vertex
- Level k: all vertices at distance exactly k from the start
This level structure is preserved in the BFS spanning tree. The tree edges always connect vertices in consecutive levels (level k to level k+1), making BFS trees particularly useful for finding shortest paths in unweighted graphs.
Why BFS Matters
Unlike depth-first search (which dives deep), BFS explores systematically by distance. This makes BFS spanning trees ideal for:
- Finding shortest paths
- Analyzing distance relationships
- Understanding the "breadth" of connectivity from a source
Key Takeaway: Breadth-first search constructs a spanning tree by exploring vertices level by level, creating a natural distance hierarchy from the starting vertex.