BFSBaum

BFSBaum, or BFS tree, is the spanning tree obtained when a breadth-first search is executed on a graph G starting from a designated root vertex r. As BFS progresses, vertices are discovered in nondecreasing distance from r, and for every vertex v that is first encountered via a predecessor u, the edge (u, v) becomes part of the BFS tree. The root has no parent, and the collection of such tree edges connects all vertices reachable from r, forming a spanning tree of the root's connected component.

Key properties: the distance from r to any vertex in the BFS tree equals the length of the shortest path from r to that vertex in G, measured in number of edges, provided the graph is unweighted. The BFS tree is not unique: different orders of exploring neighbors yield different valid trees, though all respect the same distance levels.

Algorithmic notes: constructing a BFS tree requires a queue to manage the frontier, and an array or map to record each vertex's parent. Time complexity is O(V + E) and space complexity is O(V + E) for adjacency storage and the tree representation.

Applications: BFS trees are used to compute single-source shortest paths in unweighted graphs, test reachability and connectivity, identify level structure, and serve as a basis for further graph algorithms such as minimum-height spanning trees in unweighted settings or network routing heuristics.