## Overview

** Prim’s algorithm** and

**are greedy algorithms used to find the minimum spanning tree in a weighted graph.**

*Kruskal’s algorithm**Prim’s*and

*Kruskal’s*algorithms have many use cases they are used in solving traveling salesman problems,

*LAN*networks,

*TV*networks, and in general for any network where we need to find the least cost subset of this network such that any two nodes are connected.

## Scope

- This article gives a brief introduction to
*Prim’s*algorithm and*Kruskal’s*algorithm. - It explains
*Prim’s*and*Kruskal’s*algorithms with corresponding examples. - It also explains the key differences between
*Prim’s*and*Kruskal’s*algorithms and similarities as well. - We learn about some of the use cases of
*Prim’s*and*Kruskal’s*algorithms in real-life scenarios like designing a*LAN*network.

## 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.

### Conclusion

- We conclude that
*Prim’s*and*Kruskal’s*algorithms are greedy algorithms used for finding the minimum spanning tree of a given weighted graph. *Prim’s*algorithm adds nodes while*Kruskal’s*algorithm adds edges which calculates the minimum spanning tree.*Prim’s*algorithm runs faster in the case of dense graphs while*Kruskal*runs faster in the case of sparse graphs.*Prim’s*algorithm is a little complex in implementation as compared to*Kruskal’s*algorithm.- Space complexity of
*Prim’s*algorithm is relatively higher than*Kruskal’s*algorithm.

## FAQs

Q. **Why does Prim’s algorithm is faster on denser graphs while Kruskal’s algorithm on sparse graphs?**

A: *Prim’s* algorithm is faster on dense graphs because it just traverses the adjacent nodes for each node and it does not have to sort the edges as in the case of *Kruskal*, therefore *Prim’s* algorithm is faster in calculating the minimum spanning tree for dense graphs.

*Kruskal* Algorithm is faster in the case of sparse graphs because for sparse graphs the number of edges is smaller and hence sorting the edges is more efficient than selecting an adjacent node for each node.