CODEWITHSUNDEEP
minimum-spanning-treeprims-algorithmkruskals-algorithm
user1687035
user1687035

Reputation: 253

Prim's and Kruskal's algorithm

Prim's and Kruskal's algorithm both produce the minimum spanning tree. According to the cut property, the total cost of the tree will be the same for these algorithms, but is it possible that these two algorithms give different MST with the same total cost, given that we choose it in alphabetic order when faced with multiple choices. for example, we compare max(source,dest), for edges A->B and B->C, we compare A from A->B and B from B->C.

Thank you

Upvotes: 4

Views: 16722

Answers (2)

Isabel Amat
Isabel Amat

Reputation: 21

It is definitely possible for one graph to have multiple MSTs, so long as those different representations of the MSTs have the same total weight. Otherwise, the one with the lower total weight would be the true MST and the other would no longer be an MST.

Because Prim's and Kruskal's algorithms have different steps, it is possible that they would choose different edges of the same weight during the actual traversal, yet still end with the same total weight.

However, if you add the restriction that you stated in your question (choosing the node that comes first in the alphabet) the MST for Prim's and Kruskal's should be the same tree, for each of the decisions, even if they are the same weight, would prefer the same edge for both Kruskal's and Prim's.

Upvotes: 0

jma127
jma127

Reputation: 1432

Assuming that your comparator handles the case where both edges are equal in cost and have the same max(source, dest) character, it will never declare any two edges equal. For there to be the possibility of multiple MSTs, at least two edges in the graph must be equal. Therefore, the MST is unique, and both Prim's and Kruskal's algorithm will return the same result.

On the other hand, if your comparator declares the edges A->B (cost 1) and A->C (cost 1) equal, than there is a possibility that the algorithms will generate different MSTs, depending on which edge they consider first (A->B or A->C).

Upvotes: 6

Related Questions