Which algorithm is more efficient in constructing the minimum spanning tree of a given graph: Prim’s Algorithm or Kruskal’s Algorithm and why?

Share

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

In Prim’s, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.

In Kruskal’s, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.

Use Prim’s algorithm when you have a graph with lots of edges.

For a graph with

VverticesEedges, Kruskal’s algorithm runs inO(E log V)time and Prim’s algorithm can run inO(E + V log V)amortized time, if you use a Fibonacci Heap.Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.