The Gateway to Computer Science Excellence
+2 votes
567 views
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
in Algorithms by (169 points)
retagged by | 567 views
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.

3 Answers

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

But the cost of Both tree is Same
by Loyal (6.9k points)
0
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.
+1 vote
may differ when there are more than one possible spanning tree. But total weight is always very same
by Boss (18k points)
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. :)

by Boss (13.8k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
198,087 comments
104,737 users