Prims's Vs Kruskal's Algorithm

Prim’s Algorithm

Kruskal’s Algorithm

It begins with a Node.It begins with an edge.
It starts to build the MST Set from any of the Nodes.It starts to build the MST Set from minimum weighted vertex in the graph.
Run Faster in dense graphs.Run faster in sparse graphs.
The graph must be a connected graph.It works on the connected and disconnected graph.
Traverse the one node several times to get the minimum distance.Traverse the edge only once.
Time Complexity is O(E*V logV) with binary heap and O(E+V logV) with the Fibonacci heap.Time Complexity is O(E logV)
Binary or Fibonacci Heap, Adjencacy Matrix are used.Disjoint Set is used.
The next node included must be connected with the node we traverse.The next edge includes may or may not be connected but should not form a cycle.
Doesn’t check cycle is formed or not.The check cycle is formed or not. If formed then discard the nodes.

By Arun

One thought on “Difference Between Prim’s and Kruskal’s Algorithm”

Leave a Reply

Your email address will not be published. Required fields are marked *