2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh, thanks for the clarification; looks like I'll be approaching my problem from another angle then! $\endgroup$ – racketball Mar 23 '13 at 21:04
  • $\begingroup$ Is there a specific reason, why you don't want to use Kruskal's or Prim's algorithm? $\endgroup$ – Me. Mar 23 '13 at 21:09
  • $\begingroup$ 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. $\endgroup$ – racketball Mar 23 '13 at 21:30
  • $\begingroup$ ^ Neither for Prim nor for Kruskal connectedness is a major issue. But I see what you mean. $\endgroup$ – Me. Mar 23 '13 at 22:12
  • $\begingroup$ 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) $\endgroup$ – racketball Mar 24 '13 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.