[Solved]: DFS miniumum spanning tree

Problem Detail: 

Just a quick question,

If i were to alter the general DFS algorithm to do this:

minDFS(Vertex v) {    if (!v.getVisted())    {        v.setVisited();        Vertex temp = findClosestVertex();        graph.addEdge(v, temp);        minDFS(temp);    } } 

Would I eventually (at the end of DFS) get minimum spanning tree? I know there are other ways of getting the MST (Kruskal's, Prim's etc..),but I was just wondering if this would work.

Asked By : racketball

Answered By : Me.

No. Consider the counterexample $C_4$

$V = \{1,2,3, 4\}, E = \{ \{1,2\}, \{2,3\}, \{3, 4\}, \{1,4\} \}$

with $c(1,2) = 1, c(2,3) = 100, c(3,4) = 1, c(1,4) = 2$.

Obviously the MST is the one ST not containing $\{2,3\}$, but if your algorithm starts at 1, it goes to 2, then to 3 and then to 4 and finds a suboptimal ST containing $\{2,3\}$.

The main problem of your algorithm is that it always computes a path (i.e if there is no path of length $|V| - 1$ your algorithm can terminate without finding a ST), which the MST must not always be.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10717