In this article, we will cover the problem of Minimum Spanning Tree. In my previous post, I covered the Disjoint Set Union problem.
NOTE: To make the article fun, we have wrapped an inter-galactic fictional story around it. Don't get confused by it.
The Problem
Kapi has just conquered the universe. His childhood dream is finally a reality. Every planet of this universe is now under his control. To celebrate this glorious occasion, Kapi plans to visit each planet and take selfies with the head of that planet, who is also responsible for treating him with the best of their food items. Kapi is really eager to post these photos on social media, so he wants to finish this procession as soon as possible.
He has a graph of the universe which has planets as nodes and the distances between them as edge weights.
He is now thinking of a way to visit each and every node only once and enjoy the delicacies.
As he is the ruler of the universe, he has to announce his goals formally. So this was published in newspapers of each planet the very next day:
Lord’s Aspiration:
Given a connected undirected Graph G =( V, E ), construct a spanning tree, which is a tree that covers every vertex of G and is a subgraph of G. Furthermore, the tree must have minimum total weight, which means that the sum of weights of each edge included in the spanning tree should be minimum.
One who comes up with a correct and fast algorithm will be made the head of their respective planet.
The idea is to plan Kapi's voyage in such a way, that he has to travel the minimum distance while covering all the planets. Below we have a pictorial representation of the planets along with the paths connecting them, with different distances(depicted by the width of the connecting line. More the width of connecting line, larger the distance between planets). As you can see in the picture below, there can be so many possible paths to traverse.
Brute Forcians (Brute Force)
As usual, residents of the planet Brute Force were the first to come up with a solution. They were in favor of trying all possible combinations of the spanning trees and choosing the one which has a minimum total cost. Kapi got furious when he received a mail having a brute force code written in it.
He at once ordered the authorities to grab all of Brute Forcian's and bring it to him for punishment.
Greedy Pur - Kruskal's Algorithm
A genius named Kruskal came up with a really cool algorithm of making a minimum spanning tree. He claimed that the following steps will yield a minimum spanning tree, which can be followed to finish the voyage in minimum time, traversing the minimum distance.
-
Sort all the edges(lines connecting the planets) in non-decreasing order of weights(weight here means the value of distance).
-
Add edges to MST starting from the least weighted to max weighted ones, ensuring that no loop is formed in the process.
What attracted Kapi the most was the ability to check if the edge that is being added will form a cycle or not, in other words, it will join only the disconnected components, not the already connected ones. Mr. Kruskal assigned Disjoint set union (DSU) with this responsibility.
Disjoint sets are sets whose intersection is the empty set so it means that they don't have any element in common.
Let us go through an example:
So we start with the least weighted edge, i.e., the edge with weight 10 and add it to our MST. We proceed with 20, 30 and 40 in the similar way and as they don’t form any cycle, we keep adding them into our MST. Now the edge with weight 50 will form a loop if included in MST, and as we already have all the nodes connected in our minimum spanning tree, we will be searching for more edges skipping the edge with weight 50.
Below we have the code for this:
#include<bits/stdc++.h>
using namespace std;
#define sz 100005
int id[sz];
int root(int x)
{
while(id[x]!=x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void unify(int x,int y)
{
int parA = root(x);
int parB = root(y);
id[parA] = id[parB];
}
int kruskal(std::vector<tuple<int,int,int>> v,int edges)
{
int i,x,y,w,ans=0;
for(i=0;i<edges;i++)
{
x = get<0>(v[i]);
y = get<1>(v[i]);
w = get<2>(v[i]);
// if nodes are disconnected , add it to MST
if(root(x)!=root(y))
{
ans = ans + w;
unify(x,y);
}
}
return ans;
}
int main()
{
// make vector of tuples storing the two vertices and the weight
vector<tuple<int,int,int> >v;
int x,y,z,w,i,j;
int nodes,edges;
cin>>nodes>>edges;
for(i=0;i<edges;i++)
{
cin>>x>>y>>w;
v.push_back(make_tuple(x,y,w));
}
// sort the edges in non decreasing order
sort(v.begin(),v.end());
// initialise DSU
for(i=0;i<sz;i++)
id[i]=i;
cout<<kruskal(v,edges);
return 0;
}
Time Complexity: As we are sorting the vector of tuples, it is O(E log V).
Greedy Pur - Prim's Algorithm
Another prodigy named Mr. Prim also came up with an algorithm inspired by Dijkstra's work. He started with an arbitrary vertex and added vertices in MST as per the following rule:
1. Find the cheapest vertex that can be added to the MST and add it along with ensuring that no cycle is formed.
2. Cheapest vertex is obtained by using a priority queue while maintaining a set of visited vertices will disallow any loops.
What is better than an example:
See how both the algorithms produced the same MST, which is unique for a given graph as the edges are non-negative and unique.
So we started with node 10 (random choice, we can pick any as eventually all vertices will be included in the MST), and kept on adding vertex which was cheapest at that moment.
Below we have the code for this:
#include<bits/stdc++.h>
using namespace std;
#define sz 100005
typedef pair<int,int>p;
vector<p>v[sz];
int prim(int x)
{
priority_queue<p, vector<p>, greater<p>> pq;
int i,l,ans=0;
bool vis[sz]={false};
pq.push(make_pair(0,x));
p pick;
while(!pq.empty())
{
//pick the cheapest vertex
pick = pq.top();
pq.pop();
x = pick.second;
if(vis[x] == true)
{
continue;
}
vis[x] = true;
// include the vertex in MST
ans = ans + pick.first;
for(i=0;i<v[x].size();i++)
{
l = v[x][i].second;
if(vis[l]==false)
pq.push(v[x][i]);
}
}
return ans;
}
int main()
{
int x,y,z,w,i,j;
int nodes,edges;
cin >> nodes >> edges;
for(i=0;i<edges;i++)
{
cin >> x >> y >> w;
v[x].push_back(make_pair(w,y));
v[y].push_back(make_pair(w,x));
}
// randomly choosing 'x' as the first vertex
cout << prim(x);
return 0;
}
Time Complexity: O((V + E)log V)
As we are visiting each and every node just once => (V + E)
and as binary heaps are used to implement priority queues => log V.
Fun Corner
Radia Perlman, who is most famous for her invention of the spanning-tree-protocol (STP), which is fundamental to the operation of network bridges, while working for Digital Equipment Corporation, penned this poem:
I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree that must be sure to span
So packets can reach every LAN.
First, the root must be selected.
By ID, it is elected.
Least-cost paths from root are traced.
In the tree, these paths are placed.
A mesh is made by folks like me,
Then bridges find a spanning tree.
You may also like:
