8
$\begingroup$

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?

|cite|improve this question
$\endgroup$
13
$\begingroup$

Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily produce the same result.

|cite|improve this answer
$\endgroup$
7
$\begingroup$

If the MST is unique, all algorithms will perforce produce it.

If the MST is not unique, the outputs might differ due to different node processing orders (even two distinct implementations of the same algorithm can), but the total weights will be identical. In this case, the MST is a misnomer.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ They certainly might, but do they? $\endgroup$ – Raphael♦ Nov 19 '17 at 22:23
  • 4
    $\begingroup$ @Raphael: I answered that. $\endgroup$ – Yves Daoust Nov 19 '17 at 22:23
  • 1
    $\begingroup$ @Yves No, you didn't. You said maybe, "maybe" is not a guarantee. For example, if you have sorting algorithms, and they are stable, they do produce the same output, regardless of the algorithm used. If they are not stable they might produce same results. So the question is whether those algorithms have a sense of stability w.r.t the topic and exhibit it. $\endgroup$ – luk32 Nov 20 '17 at 15:18
  • $\begingroup$ @luk32: did you read "even two distinct implementations of the same algorithm can" ? By the way, stable sorting algorithm produce the same output because it is uniquely defined, so they have no choice. If stability is not required, the solution is not unique and different implementations may behave differently. $\endgroup$ – Yves Daoust Nov 20 '17 at 15:20
  • $\begingroup$ Fair enough, but that statement is not obvious. What makes the implementation possible to be not stable? Is there some kind of sorting involved and the stability depends on this? $\endgroup$ – luk32 Nov 20 '17 at 15:26
2
$\begingroup$

To add upon Yves Daoust's answer, the following graph

Triangle

In this graph, we have 3 nodes and 3 edges, each has the same weight. Obviously any 2 edges will form a MST for this graph. However, which two edges are chosen will depend on not only the algorithm, but the implementation of the algorithm. For instance, if I store the nodes in a list, I may visit them in a different order than if I stored the nodes in a set, even if I use the same MST algorithm from that point on.

In fact, if my implementation relies on pointer arithmetic (which some containers in some languages do), I may even pick a different MST each time I run the algorithm!

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Note that the original post states that edges have unique weight; this of course guarantees a unique MST. $\endgroup$ – wchargin Nov 20 '17 at 3:45
  • $\begingroup$ That last point also applies when using e.g. set or dict in Python 3.3+: hashes are salted with a value that is different for every run to make denial-of-service attacks harder. $\endgroup$ – Jasmijn Nov 20 '17 at 9:39
  • $\begingroup$ @YvesDaoust Terribly sorry about that! $\endgroup$ – Cort Ammon - Reinstate Monica Nov 20 '17 at 16:27
  • $\begingroup$ @CortAmmon: no worries, that happens. $\endgroup$ – Yves Daoust Nov 20 '17 at 17:21

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.