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
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.
Exercise. What about disconnected graphs?
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.
