# DFS miniumum spanning tree

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();
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.

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.

• Oh, thanks for the clarification; looks like I'll be approaching my problem from another angle then! Mar 23, 2013 at 21:04
• Is there a specific reason, why you don't want to use Kruskal's or Prim's algorithm?
– Me.
Mar 23, 2013 at 21:09
• Not really, finding the MST is required as part of a homework assignment, but we're limited on time and space, and i thought this would be faster (since i don't need to make a priority queue or get all the edges first). I'm also not guaranteed a connected graph to begin with, so Prim's is out of the question. Mar 23, 2013 at 21:30
• ^ Neither for Prim nor for Kruskal connectedness is a major issue. But I see what you mean.
– Me.
Mar 23, 2013 at 22:12
• Oh okay I see. I did have another question, maybe you could offer some insight; if my input consists only of vertices (that is, no edges), then wouldn't Kruskal's/Prim's be very ineffective? (I'd have to generate all possible edges before finding the MST) Mar 24, 2013 at 6:51