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] = uExample
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.
38+ registered 
