## Introduction

A spanning tree is a minimal graph that is connected, acyclic and undirected. It has all the vertices from the corresponding graph but has a subset of edges. A graph can have many spanning trees.

The edges of the graph are assigned a value called the weight of the edge and a spanning tree is made up of a subset of edges that connects all the vertices with minimum total weight is called a Minimum Spanning Tree.

In a minimum spanning tree, every pair of nodes is connected by a unique path, and in such a tree, if there are n vertices, then there must be n-1 number of edges. If we add any new edge without adding a new vertex, that will create a cycle.

Fig 1. A connected cyclic graph

Fig 2. Minimum spanning tree of the above graph

As shown in the above figure, Fig 1(a) is the image of a weighted graph that is connected and cyclic, and Fig 1(b) is the minimum spanning tree for the graph mentioned above.

Following are the two algorithms to find a minimum spanning tree for a given graph:

**Primâ€™s algorithm****Kruskalâ€™s Algorithm**

We will discuss both the algorithms in detail now.

## Primâ€™s Algorithm

Primâ€™s algorithm is also known as Jarnikâ€™s algorithm. It is a greedy approach to find the minimum spanning tree containing all the vertices and a subset of edges whose total weight is minimum for a weighted undirected cyclic graph. It works on the principle of going with the best next move. It works well with denser graphs.

**The steps of Primâ€™s algorithm are:**

- Initialize the visited vector for all vertex as False, Nbr vector as -1 and Dictance as infinity or a very large number.

- Firstly, take anyone vertex at random from the graph say 1 and initialize the required minimum spanning tree with that vertex by adding it to tree_edge and set visited of that vertex as True.

- Search for the neighbours j of vertex 1 and set Nbr[j] as 1 and distance[j] as the weight of edge (1, j).

- For all the remaining vertices, select and add the vertex i with visited[i] as False and distance[i] is minimum.

- Keep on updating the distance of vertex on addition of any edge in the tree with the updated minimum distance.

- Continue the previous 2 steps until all the vertices are added to our minimum spanning tree.

### Pseudocode

```
Function Prim
// Inintialize important vectors
for i = 1 to n //n is the number of vertices
visited[i] = False
Nbr[i] = -1
Distance[i] = infinity
tree_edges = [] // to store the edges considered in our minimum spanning tree
visited[1] = True //source - 1
for each edge (1,j)
Nbr[j] = 1
Distance[j] = weigth(1,j)
//for remaining vertices
for i =2 to n
choose u such that visited[u] = False
and distance[u] is minimum
visited[u] = True
tree_edge.append{(u,Nbr[u])} //add the edge
//updating the distance due to the addition of u vertex
for each edge (u,v) with visited[v] = False
if Distance[v] > weight(u,v)
Distance[v] = weigth(u,v)
Nbr[v] = u
```

### Example

For the below-given graph, we have to find the minimum spanning tree.

Fig 3. A graph to find the minimum spanning tree.

### Solution

**Step1:** First of all, we take any vertex at random, say A. We initialize our minimum spanning tree with vertex A.

**Step2:** Now, all the edges of A, the one with minimum weight, is with E, i.e.1. So we add this edge to our tree.

**Step3: **Now, for all the edges of A and E that is EF, EB, AD and AB, the one with the minimum weight is AB. So, we add AB to our tree.

**Step4:** Now again repeat the same process; we get BD

**Step5:** Repeating the same process of finding the minimum weighted edge that introduces a new vertex. We get DC.

**Step6: **Now Bc is the edge with minimum weight, but it does not introduce any new vertex to our minimum spanning tree; hence we move on to the following minimum weight edge that is EF and hence F is a new vertex we add this edge.

We stop now as all the vertices are added to the graph, and adding any more edge will create a cycle in our tree. So, this is our required minimum spanning tree using Primâ€™s algorithm. And the total weight is 1+2+2+1+5 = 12.