Detailed comparison difference

#1

may i know the diiference between kruskals and prims based on time complexity and when to use which one??

#2

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(E log V), V being the number of vertices. Kruskal’s algorithm’s time complexity is O(E logV), 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.
#3

Kindly explain the time complexity.

#4

by mistake

i have edited the time complexity of both algorithm
both have time complexity O(ElogV) However, Prim’s algorithm can be improved using Fibonacci Heaps (cf Cormen) to O(E + logV)