#algorithm

Question

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

Comments

No, only the procedure is different

---

possible when all edge weights are not distinct..

---

The difference is in one algorithm we use sorting while other uses min heap.

---

https://cs.stackexchange.com/questions/84159/do-kruskals-and-prims-algorithms-yield-the-same-minimum-spanning-tree

Answer 1

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

But the cost of Both tree is Same

Comments

I want to ask that

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.

Answer 2

may differ when there are more than one possible spanning tree. But total weight is always very same

Answer 3

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. :)