A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example of a graph where a DFS won't find the minimum spanning tree regardless of how the adjacency list is ordered. Is this correct or not? I can't come up with a counter example and intuitively it seems correct...
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Sure, if you try all possible searches you'll find the minimum spanning tree, it's just inefficient. $\endgroup$– Luke MathiesonNov 19, 2012 at 0:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No you wont. Suppose you have as graph the complete graph $K_n$ with $n\ge 4$, for simplicity we pick the $K_4$, but this construction works for all larger $n$.
Every DFS-tree of a complete graph is a path, no matter how you order the edges. But clearly you can define the weights such that a non-path is the MST. See the example below (MST in red).
