# Show that the tree resulting from BFS is a spanning tree?

Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \{ \{\text{predecessor}[u], u\} \mid u \text{ is a vertex}\}$ is a spanning tree of $G$?

• What have you tried and where did you get stuck? Note that this is a crucial part of the correctness proof for BFS, so it's probably in many textbooks. Nov 19, 2014 at 11:58

Observe that any spanning tree of $G$ contains every vertex of $G$, and has no cycles. Use induction to show that on every iteration, the process creates no cycles (and also visits every vertex).

I have no idea about data structure you are going to use, but you probably have all of your vertexes and for each vertex list of it's neighbours. A general approach should be:

After each step in your traversal check the list. If new vertex is a visited vertex then there is a loop in your graph an it's not a tree. (check your graph is a tree or not)

Another condition is to check coverage of your graph. When your traversal completed the visited list should contain a complete set of graph vertexes.(check for spanning)

• @David I just removed the paragraph that made my answer ambiguous. That was a general approach for BFS or any other traversal. Does it look better now? Nov 20, 2014 at 6:19