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
