First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS

cs.stackexchange https://cs.stackexchange.com/questions/109493

  •  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
scroll top