what are the differences between prim’s and kruskal’s algo and when to apply which algo
Difference between the 2 mst algorithms
Both Prim’s and Kruskal’s algorithm finds the Minimum Spanning Tree and follow the Greedy approach of problem-solving, but there are few major differences between them .
| PRIM’S ALGORITHM | KRUSKAL’S ALGORITHM |
|---|---|
| It starts to build the Minimum Spanning Tree from any vertex in the graph. | It starts to build the Minimum Spanning Tree from the vertex carrying minimum weight in the graph. |
| It traverses one node more than one time to get the minimum distance. | It traverses one node only once. |
| Prim’s algorithm has a time complexity of O(V2), V being the number of vertices and can be improved up to O(E + log V) using Fibonacci heaps. | Kruskal’s algorithm’s time complexity is O(E log V), V being the number of vertices. |
| Prim’s algorithm gives connected component as well as it works only on connected graph. | Kruskal’s algorithm can generate forest(disconnected components) at any instant as well as it can work on disconnected components |
| Prim’s algorithm runs faster in dense graphs. | Kruskal’s algorithm runs faster in sparse graphs. |
Pls can you explain me the last 2 points of the differences. I didn’t understand them.
Can you tell me which two points were problematic for you?
The last 2 points of your ans. Also how did you calculate the time complexity of the algorithms
There are many types of graphs, usually normal types of graphs are connected only. So, Prim’s algorithm gives connected component as well as it works only on connected graph.
Suppose there’s a connected graph and one edge which doesn’t intersect with this connected graph is added , it will be forest graph. In this Kruskal’s algorithm can generate forest(disconnected components) at any instant as well as it can work on disconnected components
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.