Prims and Kruskal Algorithm

What is Prim’s Algorithm in MST?

Prim's algorithm is used to find the minimum spanning tree for a given weighted graph. Given a weighted graph of n nodes, prim's algorithm is used to find the tree having n nodes and $n-1$ edges such that the sum of weights of these $n-1$ edges is the minimum of all possible trees.

Spanning Tree(ST):

A spanning tree of a weighted graph with $N$ nodes is a subgraph that includes all vertices of the graph with the minimum possible number of edges i.e. there is a unique path between any two nodes of the subgraph. There can be more than one spanning tree.

Minimum Spanning tree(MST):

The minimum spanning tree of a weighted graph having $N$ nodes is the spanning tree having the minimum sum of weights of all edges.

In the example below given a graph and its spanning trees

The spanning trees of the above-weighted graph are shown below

The first spanning tree has the least weight i.e. 10 and hence is the minimum spanning tree.

Prim's algorithm:

Prim's algorithm is used to find the minimum spanning tree.

It is a greedy algorithm that constructs the minimum spanning tree by selecting the most optimal edge at that point.

To read more about prim's algorithm and its implementation click here Prim's algorithm

What is the Kruskal Algorithm in MST?

Kruskal's algorithm is another greedy algorithm besides prim's which is used to find the minimum spanning tree from a given graph.

The main idea of Kruskal's algorithm is as follows:

Given a weighted graph with $N$ vertices and $E$ edges, the idea is to sort all the edges in increasing order of their weights, then we select the first $N-1$ edges such that they do not form a cycle within them.

It is guaranteed that those selected $N-1$ edges will construct the minimum spanning tree because there is no other way to include even smaller weight edges as we already considered the smallest weight $N-1$ edges.

To read more about Krushkal's algorithm click here Krushkal's algorithm

Examples

Let's go through examples of Prim's and Krushkal's algorithm one by one.

Prim’s Algorithm

Suppose you are given a weight graph as shown below, the task is to find the minimum spanning tree using Prim's algorithm, and list out all steps for finding the minimum spanning tree of the given graph.

Below are the steps of Prim's algorithm:

1. Start with any node in the graph and mark it visited and include it in the MST.

2. Iterate over all adjacent vertices of the chosen vertex which are not included in the MST and update their values and parent.

3. Repeat the above two steps until all the nodes are included in the MST.

To implement the above steps of the algorithm we need three arrays:

setMST[N]: A boolean array that keeps track of the nodes included in the MST.

value[N]: An integer array that keeps track of the minimum edge weight for a particular node.

parent[N]: An integer array that stores the parent of each node, the parent of starting node is set to -1.

Let's start simulating the algorithm for the above graph:

Initially, the status of the above-mentioned arrays is as follows:

First of all, we pick an arbitrary vertex in the graph that says 1.

The arrays will be as follows

Now, we select the edge with the least weight out of all edges going out of node 1.

The arrays will be updated as follows:

Next, we have edges $1-3$ and $2-4$ out of which we select $1-3$ because it has the least weight.

The arrays will be updated as follows:

Next, we have edges $2-4$, $3-4$, and $3-5$ out of which $2-4$ is chosen as it has the least weight.

The corresponding arrays will be updated as follows:

Next, we have edges $3-4$, $3-5$, and $4-5$ and we shall select the edge $4-5$.

The corresponding arrays will be updated as follows:

Now, we have covered all the vertices and this must be the minimum spanning tree for the above example with weight equal to the sum of elements of array value i.e. $0 + 1 + 2 + 3 + 4 = 10$ which is indeed the answer.

Kruskal Algorithm

Suppose you are given a weight graph as shown below, the task is to find the minimum spanning tree using Kruskal's algorithm, and list out all steps for finding the minimum spanning tree of the given graph.

Below are the steps of Kruskal's algorithm:

1. Sort all the edges in increasing order of their weight.
2. Select the first $N-1$ edges such that they do not form any cycle within them.

Let's see the simulation of prim's algorithm:

We start from the lowest-weight edge

Now, we choose the second-lowest weight edge.

Next, we choose the third-lowest weight edge such that it does not form a cycle.

Now, we choose the fourth-lowest weight edge such that it does not form a cycle.

Here, we have selected all the vertices, therefore, this is the minimum spanning tree and the sum of the edge weights is $1 + 2 + 3 + 4 = 10$.

Key Differences between Prims and Kruskal Algorithm

Although both prim's and Kruskal's algorithms are greedy algorithms used to find the minimum spanning tree for a given weighted graph there are few differences between prim's and Kruskal's algorithm in terms of time, space, and working mechanisms.

1. In prim's algorithm, we choose the nodes greedily i.e. the node is chosen at a point such that the edge weight for this node is minimum while in the case of Krushkal's algorithm we choose the minimum weight edges greedily.

2. In Kruskal's algorithm we sort the edges by weight in increasing order and then select the $N-1$ edges without cycle having minimum weight but in the case of Prim's algorithm, we choose the vertices considering the edge weights, and even if the number of edges goes high it still stays efficient. In the case of dense graphs, Prim's algorithm is better.

3. Time complexity for the Prim's algorithm is $O(N^2)$ while for Krushkal it is $O(ElogN)$.

4. Prim's algorithm only works on a connected graph because we need to select the adjacent node for a selected node with minimum weight, while Krushkal can work for the disconnected component as well.

Prim's Vs Kruskal's Algorithm

Prim's and Kruskal's algorithm besides having similarities also has a lot of differences in terms of their use cases, complexity, and other factors like speed.

Following are the key differences between Prim's and Kruskal's algorithms in table format.