First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS
-
05-11-2019 - |
Question
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
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange