This C++ Tutorial Explains What is a Minimum Spanning Tree (MST) Along With Prim’s and Kruskal’s Algorithms to Find MST in a Graph and Its Applications:
A Spanning tree can be defined as a subset of a graph, which consists of all the vertices covering minimum possible edges and does not have a cycle. Spanning tree cannot be disconnected.
Every connected and undirected graph has at least one spanning tree. A disconnected graph does not have a spanning tree as it is not possible to include all vertices.
=> See Here To Explore The Full C++ Tutorials list.
Table of Contents:
Spanning Tree In C++
Consider the following connected graph.
As shown above, for the given connected Graph containing 3 vertices, we have three spanning trees. In general, if N is the number of nodes in a graph, then a complete connected graph has maximum NN-2 number of spanning trees. Thus in the above graph N =3, therefore, it has 3(3-2) = 3 spanning trees.
Some of the properties of the spanning tree are listed below:
- A connected graph can have more than one spanning trees.
- All spanning trees in a graph have the same number of nodes and edges.
- If we remove one edge from the spanning tree, then it will become minimally connected and will make the graph disconnected.
- On the other hand, adding one edge to the spanning tree will make it maximally acyclic thereby creating a loop.
- A spanning tree does not have a loop or a cycle.
What Is A Minimum Spanning Tree (MST)
A minimum spanning tree is the one that contains the least weight among all the other spanning trees of a connected weighted graph. There can be more than one minimum spanning tree for a graph.
There are two most popular algorithms that are used to find the minimum spanning tree in a graph.
They include:
- Kruskal’s algorithm
- Prim’s algorithm
Let’s discuss both these algorithms!
Kruskal’s Algorithm
Kruskal’s algorithm is an algorithm to find the MST in a connected graph.
Kruskal’s algorithm finds a subset of a graph G such that:
- It forms a tree with every vertex in it.
- The sum of the weights is the minimum among all the spanning trees that can be formed from this graph.
The sequence of steps for Kruskal’s algorithm is given as follows:
- First sort all the edges from the lowest weight to highest.
- Take edge with the lowest weight and add it to the spanning tree. If the cycle is created, discard the edge.
- Keep adding edges like in step 1 until all the vertices are considered.
Pseudocode for Kruskal’s Algorithm
Given below is the pseudo-code for Kruskal’s Algorithm
Now let us see the illustration of Kruskal’s algorithm.
Now we choose the edge with the least weight which is 2-4.
Next, choose the next shortest edge 2-3.
Then we choose next edge with the shortest edge and that does not create a cycle i.e. 0-3
The next step is to choose the shortest edge so that it doesn’t form a cycle. This is 0-1.
As we can see, we have covered all the vertices and we have a spanning tree with minimum cost here.
Next, we will implement Kruskal’s Algorithm using C++.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define graph_edge pair<int,int>
class Graph {
private:
int V; // number of nodes in graph
vector<pair<int, graph_edge>> G; // vector for graph
vector<pair<int, graph_edge>> T; // vector for mst
int *parent;
public:
Graph(int V);
void AddEdge(int u, int v, int wt);
int find_set(int i);
void union_set(int u, int v);
void kruskal_algorithm();
void display_mst();
};
Graph::Graph(int V) {
parent = new int[V];
for (int i = 0; i < V; i++)
parent[i] = i;
G.clear();
T.clear();
}
void Graph::AddEdge(int u, int v, int wt) {
G.push_back(make_pair(wt, graph_edge(u, v)));
}
int Graph::find_set(int i) {
// If i is the parent of itself
if (i == parent[i])
return i;
else
//else recursively find the parent of i
return find_set(parent[i]);
}
void Graph::union_set(int u, int v) {
parent[u] = parent[v];
}
void Graph::kruskal_algorithm() {
int i, uSt, vEd;
sort(G.begin(), G.end()); // sort the edges ordered on increasing weight
for (i = 0; i < G.size(); i++) {
uSt = find_set(G[i].second.first);
vEd = find_set(G[i].second.second);
if (uSt != vEd) {
T.push_back(G[i]); // add to mst vector
union_set(uSt, vEd);
}
}
}
void Graph::display_mst() {
cout << "Edge :" << " Weight" << endl;
for (int i = 0; i < T.size(); i++) {
cout << T[i].second.first << " - " << T[i].second.second << " : "
<< T[i].first;
cout << endl;
}
}
int main() {
Graph gmst(5);
gmst.AddEdge(0,1,3);
gmst.AddEdge(0,3,3);
gmst.AddEdge(2,3,2);
gmst.AddEdge(2,4,1);
gmst.AddEdge(1,4,4);
gmst.kruskal_algorithm();
cout<<"The Minimum Spanning Tree according to Kruskal's Algorithm:"<<endl;
gmst.display_mst();
return 0;
}
Output:
The Minimum Spanning Tree (MST) according to Kruskal’s Algorithm:
Edge : Weight
2 – 4 : 1
2 – 3 : 2
0 – 1 : 3
0 – 3 : 3
Note that we have used the same example graph in the program as we have used in the illustration of Kruskal’s algorithm above. In this implementation we make use of two vectors; one to store graph and another to store the minimum spanning tree. We recursively find the edges with the least weight and add them to the MST vector till all the vertices are covered.
Prim’s Algorithm
Prim’s algorithm is yet another algorithm to find the minimum spanning the tree of a graph. In contrast to Kruskal’s algorithm that starts with graph edges, Prim’s algorithm starts with a vertex. We start with one vertex and keep on adding edges with the least weight till all the vertices are covered.
The sequence of steps for Prim’s Algorithm is as follows:
- Choose a random vertex as starting vertex and initialize a minimum spanning tree.
- Find the edges that connect to other vertices. Find the edge with minimum weight and add it to the spanning tree.
- Repeat step 2 until the spanning tree is obtained.
Pseudocode for Prim’s Algorithm
Now let us see an illustration for Prim’s algorithm.
For this, we are using the same example graph that we used in the Illustration of Kruskal’s algorithm.
Let us select node 2 as the random vertex.
Next, we select the edge with the least weight from 2. We choose edge 2-4.
Next, we choose another vertex that is not in the spanning tree yet. We choose the edge 2-3.
Now let us select an edge with least weight from the above vertices. We have edge 3-0 which has the least weight.
Next, we choose an edge with the least weight from vertex 0. This is the edge 0-1.
From the above figure, we see that we have now covered all the vertices in the graph and obtained a complete spanning tree with minimum cost.
Now let us implement the Prim’s algorithm in C++.
Note that in this program as well, we have used the above example graph as the input so that we can compare the output given by the program along with the illustration.
The program is given below:
#include <iostream>
#include <cstring>
using namespace std;
#define INF 9999
// graph contains 5 vertices
#define V 5
// an array G that stores adjacency matrix for input graph
int G[V][V] = {
{0, 3, 0, 3, 0},
{3, 0, 0, 0, 4},
{0, 0, 0, 2, 1},
{3, 3, 2, 0, 0},
{0, 4, 1, 0, 0}};
int main () {
int num_edge; // number of edge
// mst_vertex - array to track vertices selected for spanning tree
int mst_vertex[V];
// set selected false initially
memset (mst_vertex, false, sizeof (mst_vertex));
// set number of edge to 0
num_edge = 0;
//let 0th vertex be the first to be selected
mst_vertex[0] = true;
int x; // row
int y; // col
// print details of MST
cout<<"The Minimum Spanning Tree as per Prim's Algorithm:"<<endl;
cout << "Edge" << " : " << "Weight";
cout << endl;
while (num_edge < V - 1) {
//Prim's algorithm code
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (mst_vertex[i]) {
for (int j = 0; j < V; j++) {
if (!mst_vertex[j] && G[i][j]) { // not in mst_vertex 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;
mst_vertex[y] = true;
num_edge++;
}
return 0;
}
Output:
The Minimum Spanning Tree as per Prim’s Algorithm:
Edge : Weight
0 – 1 : 3
0 – 3 : 3
3 – 2 : 2
2 – 4 : 1
Applications Of Spanning Tree
Some of the applications of Minimum Spanning Trees are as follows:
#1) Communications Network Setup: When we want to set up a communication network using communication links, then the cost of setting up communication links between two points is best determined using an MST.
#2) Cluster Analysis: It can be used to solve the K-clustering problem by finding a minimum spanning tree and deleting the k-1 most expensive edges.
#3) Laying Out Road/Rail Networks: When we lay various road or rail networks between or within cities, the cost of the project is a very important factor. We can find the best path with minimum cost using minimum spanning trees.
#4) Planning Housing Facilities: Facilities like electricity, water, sewage, etc. to be provided to a number of houses also require to be at optimum cost and this is done using an MST.
#5) Solving the Travelling Salesman Problem: We can use an MST to solve the traveling salesman problem which requires to visit each point at least once.
Conclusion
The minimum spanning tree is the subset of graph g and this subset has all the vertices of the graph and the total cost of edges connecting the vertices is minimum.
We discussed two algorithms i.e. Kruskal’s and Prim’s, to find the minimum spanning tree from the graph. The Applications of the spanning tree were also explained here in this tutorial.
=> Check Out The Best C++ Training Tutorials Here.