Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?
$\begingroup$
$\endgroup$
4
asked Nov 19, 2017 at 20:55
-
3$\begingroup$ Yes, and they seem to produce the same MST. But that's not definitive. $\endgroup$– Death_by_Ch0colateNov 19, 2017 at 21:15
-
2$\begingroup$ Ok, that is true, just checking. $\endgroup$– EvilNov 19, 2017 at 22:23
-
$\begingroup$ The answer remains positive even if we remove the condition "no negative path" $\endgroup$– John L.Aug 5, 2018 at 14:47
-
$\begingroup$ Please check Are all minimum spanning trees reachable by Kruskal and Prim? and When is the minimum spanning tree for a graph not unique $\endgroup$– John L.Aug 17, 2018 at 19:26
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
answered Nov 19, 2017 at 21:40
$\begingroup$
$\endgroup$
6
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.
-
1
-
4$\begingroup$ @Raphael: I answered that. $\endgroup$– user16034Nov 19, 2017 at 22:23
-
3$\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$– luk32Nov 20, 2017 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$– user16034Nov 20, 2017 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$– luk32Nov 20, 2017 at 15:26
$\begingroup$
$\endgroup$
4
To add upon Yves Daoust's answer, the following graph
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!
-
1$\begingroup$ Note that the original post states that edges have unique weight; this of course guarantees a unique MST. $\endgroup$– wcharginNov 20, 2017 at 3:45
-
$\begingroup$ That last point also applies when using e.g.
setordictin Python 3.3+: hashes are salted with a value that is different for every run to make denial-of-service attacks harder. $\endgroup$– JasmijnNov 20, 2017 at 9:39 -
-
$\begingroup$ @CortAmmon: no worries, that happens. $\endgroup$– user16034Nov 20, 2017 at 17:21