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$?

  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Nov 19 '14 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)

  • $\begingroup$ Please re-read the question. This doesn't answer it at all. $\endgroup$ Nov 19 '14 at 12:00
  • $\begingroup$ @DavidRicherby Can you explain more? It says there is a tree(or generally a graph) that needs to be spanning. My answer is two conditions must satisfy. What's wrong?! $\endgroup$
    – muradin
    Nov 19 '14 at 12:45
  • $\begingroup$ The question specifically asks about whether the tree generated by BFS is spanning. You talk about some other tree generated by some other algorithm. $\endgroup$ Nov 19 '14 at 17:42
  • $\begingroup$ @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? $\endgroup$
    – muradin
    Nov 20 '14 at 6:19
  • $\begingroup$ Maybe I'm misunderstanding but you seem to be talking about how to use BFS to determine whether a graph is a tree. That's not what's being asked about: the question is asking how to prove that the subgraph defined by the edges that BFS moves along to find new nodes is a spanning tree. $\endgroup$ Nov 20 '14 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy