# Prims and Kruskal algorithm for Maximum Spanning Tree

## Introduction

A spanning tree is a subgraph of a graph that is a tree. By tree, we mean if N denotes the number of vertices in a graph then the number of edges in the spanning tree is equal to N - 1. A graph can have more than one minimum spanning tree. A minimum spanning tree for a weighted graph is the one that contains edges in such a way that the sum of edges comes out to be as minimum as possible.

There are majorly two algorithms used to determine the minimum spanning tree of a graph. These algorithms are described below in detail:

## Prim’s algorithm

Prim’s algorithm is a greedy algorithm that is used to determine the minimum spanning tree (MST). This algorithm begins with an empty spanning tree. One set contains the vertices which are not part of the minimum spanning tree yet and the other set contains the vertices which are already part of the minimum spanning tree.

In each step, the edges that connect two sets are selected, and such an edge is selected out of these edges that has the minimum weight. After choosing the ideal edge, the edge is completely shifted to the MST set.

### Implementation

Below is the step by step process to implement Prim’s algorithm:

1. Make a set and let’s call it mst. This keeps the record of the vertices already included in MST.

2. Now for all the vertices in the graph assign a key value. Mark all the key values as INFINITE.

3. For the first vertex to be picked, assign the key value as 0.

4. In the mst set do the following operations:

• Select a vertex V which is not a part of the MST set and has the minimum key value.
• Include this vertex V in the MST.
• Now update the key value for all the direct neighbor vertices

5. At the end you will get the minimum spanning tree of the graph.

## Kruskal’s algorithm for MST

Like Prim’s algorithm, Kruskal algorithm is also a greedy algorithm. Kruskal's algorithm is based upon sorting.

### Implementation

Below is the step by step process for the kruskal’s algorithm:

1. The very first step is to sort the edges of the graph in ascending order of the weight.

2. Now select the smallest edge. Check whether there exists a cycle by including the current edge in the minimum spanning tree. If including this edge in the spanning tree doesn’t create any cycle then include this edge otherwise discard this edge.

3. Keep traversing the edges in the sorted order and repeat step 2.

4. At the end you will get the minimum spanning tree of the given graph.

Both Prim’s and Kruskal algorithms are used to determine the minimum spanning tree of a graph, yet both differ from each other on certain points. Some of the major differences between them are discussed below:

## Differences

 Prim’s algorithm Kruskal’s algorithm This algorithm starts building the minimum spanning tree by picking any vertex in the graph. This algorithm starts building the minimum spanning tree by picking the vertex having minimum weight. The Prim’s algorithm works only on connected graphs. Kruskal’s algorithm can work on connected as well as disconnected graphs as well. The Prim’s algorithm gives better execution time in dense graphs. Kruskal's algorithm runs faster for sparse graphs. The list data structures are preferred by Prim’s algorithm. Kruskal's algorithm prefers the head data structure. Prim’s algorithm can solve problems like traveling salesmen. Kruskal’s algorithm can solve problems like a TV network. Prim’s algorithm adds the nodes in its algorithm. Kruskal’s algorithm adds the edges in its algorithm.

## Conclusion

In this article, we discussed Prim’s and Kruskal’s algorithms. Although both are greedy algorithms, they have many key differences between them. We believe that you must have enjoyed this tutorial.