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$
$\endgroup$
1
-
$\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$– RaphaelCommented Nov 19, 2014 at 11:58
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
5
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$ Commented Nov 19, 2014 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$– muradinCommented Nov 19, 2014 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$ Commented Nov 19, 2014 at 17:42
-
$\begingroup$ @David I just removed the paragraph that made my answer ambiguous. That was a general approach for
BFSor any other traversal. Does it look better now? $\endgroup$– muradinCommented Nov 20, 2014 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$ Commented Nov 20, 2014 at 9:22