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

Finding Spanning Trees: Breadth-First Search

Apply breadth-first search (BFS) to build spanning trees and understand level structure.

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:

  1. Start at any vertex v (the root)
  2. Explore all vertices adjacent to v (level 1)
  3. Mark edges used to reach new vertices—these become tree edges
  4. Continue layer by layer, only adding edges that reach previously unvisited vertices
  5. 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.