245. Can Prim and Kruskal produce different minimum spanning trees?
MediumGraph algorithms
Technical
Show model answer
Yes, when some edge weights are equal. Ties can be broken differently (Kruskal by sort order, Prim by which vertex the heap returns), and with ties a graph can have several MSTs. Example: a triangle with all weights 1 has three MSTs, and the two algorithms may pick different pairs of edges.
All MSTs have the same total weight, and in fact the same multiset of edge weights. If all weights are distinct the MST is unique, so both algorithms must return the same tree.