2 votes 2 votes Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not. Algorithms minimum-spanning-tree algorithms kruskals-algorithm prims-algorithm + – Geet asked Oct 26, 2016 • retagged Jul 10, 2019 by Cristine Geet 1.6k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented Oct 26, 2016 reply Follow Share No, only the procedure is different 0 votes 0 votes papesh commented Oct 26, 2016 reply Follow Share possible when all edge weights are not distinct.. 1 votes 1 votes Sushant Gokhale commented Oct 28, 2016 reply Follow Share The difference is in one algorithm we use sorting while other uses min heap. 1 votes 1 votes smsubham commented Dec 17, 2019 reply Follow Share https://cs.stackexchange.com/questions/84159/do-kruskals-and-prims-algorithms-yield-the-same-minimum-spanning-tree 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Yes, In case if they have more than one Spanning Tree But the cost of Both tree is Same Shubham Pandey 2 answered Oct 26, 2016 Shubham Pandey 2 comment Share Follow See 1 comment See all 1 1 comment reply Geet commented Oct 26, 2016 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes may differ when there are more than one possible spanning tree. But total weight is always very same Aboveallplayer answered Oct 28, 2016 Aboveallplayer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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. :) Devshree Dubey answered Oct 26, 2016 Devshree Dubey comment Share Follow See all 0 reply Please log in or register to add a comment.