Log In
2 votes
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
in Algorithms
retagged by
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.

3 Answers

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

But the cost of Both tree is Same
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
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:

Hope it helps u. :)

Related questions

2 votes
1 answer
5 votes
1 answer
Given graph using Prim’s or Kruskal’s algorithm, find out that how many distinct minimum cost spanning trees are possible___? My answer was 1 and given is 2 ,what I am missing ? Edit:I had confirmed with it and answer is only one tree possible.
asked Jan 2, 2018 in Algorithms sunil sarode 704 views
3 votes
2 answers
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
asked Jan 24, 2017 in Algorithms Kapil 2.1k views