BFS Tree and Parent Tracking
What You'll Learn
You'll learn how BFS naturally creates a tree structure by tracking parent relationships, and how to distinguish between different types of edges encountered during traversal.
The Core Idea
When BFS explores a graph starting from a source vertex, it discovers vertices level by level. As each vertex is discovered, we can track which vertex led us there — its parent. This creates a BFS tree: a subset of the graph's edges that form a tree rooted at the source.
Think of it like a family tree of discovery. When you discover your friend's friend, your friend becomes the "parent" in this exploration tree. This parent-child relationship traces back the shortest path to where you started.
Building the BFS Tree
As BFS runs, we maintain a parent array or dictionary. When we discover a new vertex v from vertex u, we record parent[v] = u. The source vertex has no parent (often marked as null or -1).
Edge Classification
During BFS, every edge falls into one of two categories:
- Tree edges: Edges that connect a parent to its child in the BFS tree. These are edges we use to discover new vertices.
- Cross edges: Edges that connect vertices already discovered at the same level or adjacent levels, but not in a parent-child relationship. These edges are "rejected" because they don't lead to new discoveries.
Unlike edges in the original graph, the BFS tree has exactly n-1 edges for n reachable vertices — that's the tree property!
Why Track Parents?
Parent tracking enables path reconstruction. To find the shortest path from source to any vertex v, simply follow the parent pointers backward: v → parent[v] → parent[parent[v]] → ... → source, then reverse.
Key Takeaway: The BFS tree captures the shortest-path structure of an unweighted graph through parent relationships, distinguishing tree edges (which form the discovery tree) from cross edges (which don't).