the BFS tree

Breadth-first search explores a graph in rings: first the start vertex, then everyone one edge away, then everyone two edges away, and so on, like ripples spreading on a pond. As it spreads it discovers each new vertex through exactly one edge — the edge it first arrived by. If you keep only those discovery edges and throw the rest away, what remains is a tree rooted at the start, and that is the BFS tree. It is the skeleton of where the search went and how it got there.

Here is the mechanism. BFS keeps a queue, initially holding just the source s, and marks s visited at distance 0. Repeatedly it dequeues a vertex u and looks at u's neighbours; any neighbour v not yet visited is marked visited, given distance d(u)+1, recorded with parent u, and enqueued. Because a queue is first-in-first-out, every vertex at distance k is fully processed before any vertex at distance k+1 is touched — that is the invariant that makes the rings clean. The parent pointers form the BFS tree: following parents from any vertex back to s traces the path BFS found, and crucially that path has the fewest possible edges, because BFS reaches each vertex on the earliest (shortest) ring. Any non-tree edge in an undirected graph connects two vertices whose BFS levels differ by at most one — there are no edges that jump across two or more levels, which is exactly why the level numbers equal true distances.

The BFS tree matters because its structure is the answer to several questions at once: the depth of a vertex in the tree is its shortest-path distance in edges from the source, the tree itself is a sparse subgraph (n-1 edges) that preserves all those shortest distances, and the level numbers let you test bipartiteness in one pass. It runs in O(n + m) with an adjacency list. The honest caveat: 'shortest' here means fewest edges, valid only when every edge counts the same. Give edges differing weights and the BFS tree no longer gives cheapest paths — that is Dijkstra's job, not BFS's.