Prims and Kruskal Algorithm | Difference

Important Concepts on Prim’s and Kruskal’s Algorithms-

 

Before you go through this article, make sure that you have gone through the previous articles on Prim’s Algorithm and Kruskal’s Algorithm.

In this article, we will discuss few important concepts on Prim’s Algorithm and Kruskal’s Algorithm which are important from the examination point of view.

 

Question-01:

 

Will both Prim’s Algorithm and Kruskal’s Algorithm always produce the same Minimum Spanning Tree (MST) for any given graph?

 

Solution-

 

The following two cases are possible-

 

Case-01: When all the edge weights are distinct-

 

If all the edge weights are distinct, then both the algorithms are guaranteed to find the same i.e. unique MST.

 

Example-

Consider the following example-

 

 

The application of both the algorithms on the above graph will produce the same MST as shown.

This example clearly illustrates when all the edge weights are distinct, both the algorithms always produces the same MST having the same cost as shown.

 

Case-02: When all the edge weights are not distinct-

 

If all the edge weights are not distinct, then both the algorithms may not always produce the same i.e. unique MST but the cost of the MST produced would always be same in both the cases.

 

Example-

Consider the following example-

 

 

This example clearly illustrates when in the given graph, all the edge weights are not distinct, different MSTs could be produced by both the algorithms as shown but the cost of the resulting MSTs from both the algorithms would always be same.

 

Question-02:

 

Which algorithm is preferred- Prim’s Algorithm or Kruskal’s Algorithm?

 

Solution-

 

  • Kruskal’s Algorithm is preferred when the graph is sparse i.e. when there are less number of edges in the graph like E = O(V) or when the edges are already sorted or can be sorted in linear time.
  • Prim’s Algorithm is preferred when the graph is dense i.e. when there are large number of edges in the graph like E = O(V2) because we do not have to pay much attention to the cycles by adding an edge as we primarily deal with the vertices in Prim’s Algorithm.

 

Question-03:

 

Difference between Prim’s Algorithm and Kruskal’s Algorithm.

 

Solution-

 

Prim’s AlgorithmKruskal’s Algorithm
In Prim’s Algorithm, the tree that we are making or growing always remains connected.In kruskal’s Algorithm, the tree that we are making or growing usually remains disconnected.
Prim’s Algorithm will grow a solution from a random vertex by adding the next cheapest vertex to the existing tree.Kruskal’s Algorithm will grow a solution from the cheapest edge by adding the next cheapest edge to the existing tree / forest.
Prim’s Algorithm is faster for dense graphs.Kruskal’s Algorithm is faster for sparse graphs.

 

To gain better understanding of these concepts on Prim’s Algorithm and Kruskal’s Algorithm,

Watch this video

Download the handwritten notes of “Important Concepts on Prim’s Algorithm and Kruskal’s Algorithm” here-

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Prims and Kruskal Algorithm | Difference
Article Name
Prims and Kruskal Algorithm | Difference
Description
Prim's and Kruskal Algorithm are the two greedy algorithms that are used for finding the MST of given graph. Difference between Prims and Kruskal Algorithm. Prims and Kruskal Algorithm with example.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-