A graph can have multiple spanning trees and the spanning tree resulting from a depth-first search depends on the order in which edges are processed. Can every possible spanning tree of a given graph be produced from that graph if the edge processing order is determined appropriately?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Consider a complete graph $K_n$. Then a depth-first search can only create a linear-path spanning tree, no matter what the edges processing order is.
-
$\begingroup$ Another easy example can be a cycle $C_n$. $\endgroup$– codeRCommented Apr 9 at 11:05
-
$\begingroup$ @codeR all spanning trees of a cycle $C_n$ can be obtained using DFS if you can choose edge ordering AND starting vertex. $\endgroup$ Commented Apr 9 at 13:19
-
$\begingroup$ Yes, indeed, if you change the start vertex. But the question only asks about selecting edges in different order once you start. $\endgroup$– codeRCommented Apr 9 at 14:09