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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Oh, thanks for the clarification; looks like I'll be approaching my problem from another angle then! $\endgroup$
    – racketball
    Mar 23, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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