# #algorithm

772 views
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.

retagged
0
No, only the procedure is different
1
possible when all edge weights are not distinct..
0
The difference is in one algorithm we use sorting while other uses min heap.

1 vote
Yes, In case if they have more than one Spanning Tree

But the cost of Both tree is Same
0

When we apply Prim's and Kruskal's algorithms on the same graph. Then the MST generated by Prim's algorithm and the MST generated by Kruskal's algorithm can be same or not? Explain it.
1 vote
may differ when there are more than one possible spanning tree. But total weight is always very same

It's true tat only the procedure is different. However in Krushkal's algorithm sorting is done as regards the minimum edge is taken first. But in Prim's algorithm this is not done. The major difference takes occurs when their comparison is made on the basis of time complexity. The resultant minimum spanning tree which is obtained is the same.

Please kindly refer the link below for more detailed explanation which are given as under:

http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

Hope it helps u. :)

## Related questions

1
714 views
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?