Minimum Spanning Tree for Graph in C++
By Zeeshan AlamIn this tutorial, we will learn about the Spanning Tree of the graph and its properties. We will also learn about the Minimum spanning tree for graph in C++ and its implementation using Prim’s algorithm and Kruskal’s algorithm.
We will take some examples to understand the concept in a better way.
Spanning Tree
Spanning tree is the subset of graph G which has covered all the vertices V of graph G with the minimum possible number of edges. Hence we say that a spanning tree doesn’t contain any loop or cycle and it cannot be disconnected.
For a disconnected graph, there will be no spanning tree possible because it is impossible to cover all the vertices for any disconnected graph.
So, for every connected and undirected graph has at least one spanning tree is possible.
Hence some properties of spanning tree:-
- Spanning tree has V-1 number of edges where V is the number of vertices.
- For a complete and undirected graph has maximum possible spanning tree for n number of vertices will be nn-2
- Spanning tree doesn’t have any loops and cycle.
Now see the diagram,
spanning tree
Weight of the spanning tree is the sum of all the weight of edges present in spanning tree.
Minimum spanning tree in C++
For weighted graph G=(V,E), where V={v1,v2,v3,…..} E={e1,e2,e3,e4………}
Minimum spanning tree is defined by a spanning tree which has minimum weight than all others spanning trees weight of the same graph.
Here we will learn about the two most important algorithms to find the minimum spanning the tree of graph G,
- PRIM’S algorithm.
- KRUSKAL’S algorithm.
Here we see the example of weighted Graph G and use the algorithm to find the MST.
Minimum Spanning tree
Note: If all the edges have distinct cost in graph so, prim’s and kruskal’s algorithm produce the same minimum spanning tree with same cost but if the cost of few edges are same then prim’s and kruskal’s algorithm produce the different minimum spanning tree but have similiar cost of MST.
First, we will focus on Prim’s algorithm.
Prim’s algorithm
Prim’s algorithm is a greedy approach method for minimum spanning tree which finds the local optimum path to obtain the global optimum solution.
The basic idea to implement the Prim’s algorithm for minimum spanning tree:-
- Initialise to choose a random vertex.
- Then select the shortest edges which connect new vertex and add it to MST(minimum spanning tree).
- Repeat step 2 until all vertex are not visited.
Let’s focus on pseudocode,
S={ }; //initialize spanning tree set with NULL
P={starting vertex}; //contain the starting vertex
Visit[ ] ; //initialize the visit array to false
Visit[starting vertex]=true ; //make starting vertex visit true
While(P!=V) //loop until all the vertex is not visited
Select the least cost edge(u,v) where u belongs to P and v belongs to V-P ;
Visit[v]=true ;
S=S U {(u,v)} ;
P=P U {v} ;Now we will understand this algorithm through the example where we will see the each step to select edges to form the minimum spanning tree(MST) using prim’s algorithm.
Here we look that the cost of the minimum spanning tree is 99 and the number of edges in minimum spanning tree is 6.
In above diagram we take alphabet A,B,C,D,E,F,G for vertex which is similiar to 0,1,2,3,4,5,6 for vertex and we will see 0,1,2,3,4,5,6 in coding section.
Here we can see the code implementation of PRIM’S algorithm.
#include <iostream>
#include<bits/stdc++.h>
#include <cstring>
using namespace std;
// number of vertices in graph
#define V 7
// create a 2d array of size 7x7
//for adjacency matrix to represent graph
int main () {
// create a 2d array of size 7x7
//for adjacency matrix to represent graph
int G[V][V] = {
{0,28,0,0,0,10,0},
{28,0,16,0,0,0,14},
{0,16,0,12,0,0,0},
{0,0,12,22,0,18},
{0,0,0,22,0,25,24},
{10,0,0,0,25,0,0},
{0,14,0,18,24,0,0}
};
int edge; // number of edge
// create an array to check visited vertex
int visit[V];
//initialise the visit array to false
for(int i=0;i<V;i++){
visit[i]=false;
}
// set number of edge to 0
edge = 0;
// the number of edges in minimum spanning tree will be
// always less than (V -1), where V is the number of vertices in
//graph
// choose 0th vertex and make it true
visit[0] = true;
int x; // row number
int y; // col number
// print for edge and weight
cout << "Edge" << " : " << "Weight";
cout << endl;
while (edge < V - 1) {//in spanning tree consist the V-1 number of edges
//For every vertex in the set S, find the all adjacent vertices
// , calculate the distance from the vertex selected.
// if the vertex is already visited, discard it otherwise
//choose another vertex nearest to selected vertex.
int min = INT_MAX;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (visit[i]) {
for (int j = 0; j < V; j++) {
if (!visit[j] && G[i][j]) { // not in selected and there is an edge
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
cout << x << " ---> " << y << " : " << G[x][y];
cout << endl;
visit[y] = true;
edge++;
}
return 0;
}OUTPUT
Edge : Weight 0 ---> 5 : 10 5 ---> 4 : 25 4 ---> 3 : 22 3 ---> 2 : 12 2 ---> 1 : 16 1 ---> 6 : 14
Now we will look at Kruskal’s algorithm.
Kruskal’s algorithm
Kruskal’s algorithm is also a greedy approach method for minimum spanning tree and similar to prim’s that which find the local optimum to find the global optimum.
There is little bit difference in Kruskal algorithm than prim’s algorithm is that in Kruskal’s algorithm we firstly sorted all edges based on weights of edges and further proceed for find MST.
The basic idea to implement the Kruskal’s algorithm for minimum spanning tree:-
- Firstly sorted the all the edges according to weigh of edges.
- Then pick the edges one by one in non-decreasing order and add selected edge in MST if it not produce the cycle.
- Repeat step 2 until all vetex not added in MST.
Let’s see the pseudo code,
S={ }; //contain the spanning tree
P={ }; //contain the vertex
E is set contain the edges in sorted order
while(E is not empty)
select edge(u,v) one by one
check if it produces cycle or not //use the union mechanism to check if u and v have the same parent make cycle otherwise not make cycle
if cycle does not produce then do
S=S U {(u,v)};
P=P U {v};Now we will understand this algorithm through the example where we will see each step to select edges to form the minimum spanning tree using Kruskal’s algorithm.
Here we look that the cost of the minimum spanning tree is 99 and the number of edges is 6.
Here we can see the code implementation for Kruskal’s algorithm.
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 1000;
int id[MAX], nodes, edges; //array id is use for check the parent of vertex;
pair <long long, pair<int, int> > p[MAX];
//initialise the parent array id[]
void init()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x) //if x is not itself parent then update its parent
{
id[x] = id[id[x]];
x = id[x];
}
return x; //return the parent
}
//function for union
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
//function to find out the edges in minimum spanning tree and its cost
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(root(x) != root(y))
{
minimumCost += cost;
cout<<x<<" ----> "<<y<<" :"<<p[i].first<<endl;//print the edges contain in spanning tree
union1(x, y);
}
}
return minimumCost;
}
int main()
{
int x, y;
long long weight, cost, minimumCost;
init();
cout <<"Enter Nodes and edges"<<endl;
cin >> nodes >> edges;
//enter the vertex and cost of edges
for(int i = 0;i < edges;++i)
{
cout<<"Enter the value of X, Y and edges"<<endl;
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
//sort the edges according to their cost
sort(p, p + edges);
minimumCost = kruskal(p);
cout <<"Minimum cost is "<< minimumCost << endl;
return 0;
}OUTPUT
Enter Nodes and edges 7 9 Enter the value of X, Y and edges 0 5 10 Enter the value of X, Y and edges 5 4 25 Enter the value of X, Y and edges 4 3 22 Enter the value of X, Y and edges 3 2 12 Enter the value of X, Y and edges 2 1 16 Enter the value of X, Y and edges 1 0 28 Enter the value of X, Y and edges 1 6 14 Enter the value of X, Y and edges 6 4 24 Enter the value of X, Y and edges 3 6 18 0 ----> 5 :10 3 ----> 2 :12 1 ----> 6 :14 2 ----> 1 :16 4 ----> 3 :22 5 ----> 4 :25 Minimum cost is 99
Important points:
- Kruskal’s algorithm is prefered when the graph is sparse or when the graph contain the less number of edges .
- Prim’s algorithm is prefered when the graph is dense or when the graph contain the more numbers of edges.
Application of minimum spanning tree:-
- For network designing.
- To perform the clustering analysis.
- Help in traveling salesman problem to find the minimum path to cover all city.
You may also learn,
Leave a Reply