0
$\begingroup$

I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true?

What I tried was to do both DFS and BFS on a couple of graph and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ, that's why I ask here.

Thanks

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? It is expected of you to show your partial progress, thoughts or the obstacles you have discovered. It will help draw more better answers faster. This site is a knowledge-sharing question-and-answer place instead of a solution rendering service. Have you read the answers to how to ask a good homework question? $\endgroup$ – Apass.Jack May 17 at 21:38
  • $\begingroup$ @Apass.Jack Hey, this is not a homework, this is a test question. What I tried was to do both DFS and BFS on a couple of graph and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ, that's why I ask here. Sorry. $\endgroup$ – james F. May 18 at 10:24
  • 1
    $\begingroup$ I encourage you to read the link. (For instance, given the first sentence of your comment, perhaps you might want to read the "But my exercise isn't homework!" part.) Perhaps you might start by asking whether you can find a pattern for the number of nodes of the spanning tree constructed this way. $\endgroup$ – D.W. May 18 at 18:36
0
$\begingroup$

What I tried was to do both DFS and BFS on a couple of graphs and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ.

Indeed, the spanning trees formed by the first-visited nodes might be different from DFS and BFS. For example, try a cycle graph of four vertices. When the spanning tree are different, the number of edges is still the same for both.

You might have noticed that the number of edges is always one less than the number of vertices of the graph, either by concentration or by luck, had you been playing with connected graphs long enough.

In fact, the number of edges in every spanning tree of a connected graph is always one less than the number of vertices in that graph. This comes from the following two facts.

  • The number of edges in a tree is one less than the number of vertice of that tree.
  • The vertices in a spanning tree of a connected graph are the vertices of that graph.

Exercise. What about disconnected graphs?

$\endgroup$
  • $\begingroup$ Thanks! I tried it myself and found out that while the spanning tree I get may be different, the number of edges is always the same. And it should be the same in disconnected graphs, right? Since both BFS and DFS can't reach other components. $\endgroup$ – james F. May 20 at 10:56
  • $\begingroup$ Right. $ \quad $ $\endgroup$ – Apass.Jack May 20 at 12:19
0
$\begingroup$

The trees constructed by BFS and DFS can be different. For example, if G is the triangle graph on vertex set $\{a,b,c\}$ and the traversal starts at vertex $a$, the BFS tree has edge set $\{ab,ac\}$, while the DFS tree has edge set $\{ab,bc\}$.

The BFS tree and the DFS tree both contain the same number of edges: if the traversal starts at vertex $a$ and the connected component of the graph containing vertex $a$ has $k$ vertices, then each of these trees will contain exactly $k-1$ edges.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.