0
$\begingroup$
  • Can the Prims and Kruskal algorithms yield the same value?
  • Can every graph can use Prims and Kruskal algorithms?
$\endgroup$
  • $\begingroup$ Of course they can since the optimial is only value. $\endgroup$ – Anonymous Oct 26 '16 at 5:07
  • $\begingroup$ Kruskal is pretty easy to implement $\endgroup$ – Anonymous Oct 26 '16 at 5:20
1
$\begingroup$

Yes, Prims and Kruskal algorithms will both yield the same minimum total weight of the minimum spanning tree (MST), but may provide different, optimal MST's.

Every undirected graph can use Prims and Kruskal, but there are slight differences in the algorithms that sometimes make Prims (dense graphs) or Kruskal (sparse graph) the better choice.

See this other post for more details of the differences.

$\endgroup$
  • 2
    $\begingroup$ They don't necessarily yield the same answer. We use them to find a minimum spanning tree of a graph, and since a graph may have multiple minimum spanning trees, these may differ. $\endgroup$ – Abby Oct 26 '16 at 5:25
  • $\begingroup$ Good point, I edited it for clarity. I was thinking of the total weight of the tree, which should be the same. $\endgroup$ – RationalHusky Oct 26 '16 at 5:33

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.