Blog Details
Polash Islam
11 Oct 2024
20 min read
A Minimum Spanning Tree (MST) is a fundamental concept in graph theory that applies to connected, undirected graphs. In simple terms, a spanning tree of a graph is a subgraph that connects all the vertices together without forming any cycles, and a minimum spanning tree is a spanning tree that has the minimum possible total edge weight.
Imagine a network of cities connected by roads, where each road has a certain length (or cost). The objective is to connect all the cities with a subset of these roads such that the total length (or cost) is minimized, and there are no redundant paths forming loops. This network would be the spanning tree, and if you ensure that the total length is as small as possible, it becomes a minimum spanning tree.
In mathematical terms, for a graph G(V,E), where V is the set of vertices and E is the set of edges, a spanning tree is a subgraph that includes all the vertices (V) and (V−1) edges from E without any cycles. The minimum spanning tree is the spanning tree with the smallest sum of edge weights.
The MST problem arises in many practical scenarios where we need to optimize the construction or connection of networks while minimizing costs. Some real-world examples include:
An important aspect of MST is that it guarantees a globally optimal solution using a greedy approach. In other words, starting with the lowest-cost options and progressively building the tree ensures that the total cost is minimized while keeping the network connected.
A Minimum Spanning Tree (MST) possesses several important properties that define its structure and usage in optimization problems. Here are some of the key properties of an MST:
In the case of a connected graph with several possible spanning trees, the MST will always have the lowest possible total edge weight, but it’s important to note that if the graph has multiple edges with the same weight, multiple MSTs can exist.
There are two widely used greedy algorithms to find the Minimum Spanning Tree (MST) in a graph: Kruskal’s Algorithm and Prim’s Algorithm. Both algorithms efficiently find the MST but use different approaches to achieve this. Let's explore each one in detail.
Given a weighted, undirected, and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.
Example :
Input Format:
V = 5, edges = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {4, 2, 7}}
Result: 16
Explanation: The minimum spanning tree for the given graph is drawn below:
MST = {(0, 1), (0, 3), (1, 2), (1, 4)}
We will be implementing Kruskal’s algorithm using the Disjoint Set data structure that we have previously learned.
Now, we know Disjoint Set provides two methods named findUPar()(This function helps to find the ultimate parent of a particular node) and Union(This basically helps to add the edges between two nodes). To know more about these functionalities, do refer to the article on Disjoint Set.
The algorithm steps are as follows:
After that, we will iterate over the edge information, and for each tuple, we will apply the following operation:
Finally, we will get our answer (in the mstWt variable as used in the following code) successfully.
Note: Points to remember if the graph is given as an adjacency list we must extract the edge information first. As the graph contains bidirectional edges we can get a single edge twice in our array (For example, (wt, u, v) and (wt, v, u), (5, 1, 2) and (5, 2, 1)). But we should not worry about that as the Disjoint Set data structure will automatically discard the duplicate one.
Note: This algorithm mainly contains the Disjoint Set data structure used to find the minimum spanning tree of a given graph. So, we just need to know the data structure.
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
vector < int > rank, parent, size;
public:
DisjointSet(int n) {
rank.resize(n + 1, 0);
parent.resize(n + 1);
size.resize(n + 1);
for (int i = 0; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int findUPar(int node) {
if (node == parent[node])
return node;
return parent[node] = findUPar(parent[node]);
}
void unionByRank(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (rank[ulp_u] < rank[ulp_v]) {
parent[ulp_u] = ulp_v;
} else if (rank[ulp_v] < rank[ulp_u]) {
parent[ulp_v] = ulp_u;
} else {
parent[ulp_v] = ulp_u;
rank[ulp_u]++;
}
}
void unionBySize(int u, int v) {
int ulp_u = findUPar(u);
int ulp_v = findUPar(v);
if (ulp_u == ulp_v) return;
if (size[ulp_u] < size[ulp_v]) {
parent[ulp_u] = ulp_v;
size[ulp_v] += size[ulp_u];
} else {
parent[ulp_v] = ulp_u;
size[ulp_u] += size[ulp_v];
}
}
};
class Solution
{
public:
//Function to find sum of weights of edges of the Minimum Spanning Tree
int spanningTree(int V, vector < vector < int >> adj[])
{
// 1 - 2 wt = 5
/// 1 -> (2, 5)
// 2 -> (1, 5)
// 5, 1, 2
// 5, 2, 1
vector < pair < int,
pair < int,
int >>> edges;
for (int i = 0; i < V; i++) {
for (auto it: adj[i]) {
int adjNode = it[0];
int wt = it[1];
int node = i;
edges.push_back({
wt,
{
node,
adjNode
}
});
}
}
DisjointSet ds(V);
sort(edges.begin(), edges.end());
int mstWt = 0;
for (auto it: edges) {
int wt = it.first;
int u = it.second.first;
int v = it.second.second;
if (ds.findUPar(u) != ds.findUPar(v)) {
mstWt += wt;
ds.unionBySize(u, v);
}
}
return mstWt;
}
};
int main() {
int V = 5;
vector<vector<int>> edges = {{0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}};
vector < vector < int >> adj[V];
for (auto it: edges) {
vector < int > tmp(2);
tmp[0] = it[1];
tmp[1] = it[2];
adj[it[0]].push_back(tmp);
tmp[0] = it[0];
tmp[1] = it[2];
adj[it[1]].push_back(tmp);
}
Solution obj;
int mstWt = obj.spanningTree(V, adj);
cout << "The sum of all the edge weights: " << mstWt << endl;
return 0;
}
Given a weighted, undirected, and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.
(Sometimes it may be asked to find the MST as well, where in the MST the edge-informations will be stored in the form {u, v}(u = starting node, v = ending node).)
In order to implement Prim’s algorithm, we will be requiring an array(visited array) and a priority queue that will essentially represent a min-heap. We need another array(MST) as well if we wish to store the edge information of the minimum spanning tree.
The algorithm steps are as follows:
Priority Queue(Min Heap): The priority queue will be storing the pairs (edge weight, node). We can start from any given node. Here we are going to start from node 0 and so we will initialize the priority queue with (0, 0). If we wish to store the mst of the graph, the priority queue should instead store the triplets (edge weight, adjacent node, parent node) and in that case, we will initialize with (0, 0, -1).
Visited array: All the nodes will be initially marked as unvisited.
Sum variable: It will be initialized with 0 and we wish that it will store the sum of the edge weights finally.
MST array(optional): If we wish to store the minimum spanning tree(MST) of the graph, we need this array. This will store the edge information as a pair of starting and ending nodes of a particular edge.
Note: We can start from any node of our choice. Here we have chosen node 0.
Note: Points to remember if we do not wish to store the mst(minimum spanning tree) for the graph and are only concerned about the sum of all the edge weights of the minimum spanning tree:
Example :
Input Format:
V = 5, edges = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {4, 2, 7}}
Result: 16
Explanation:
The minimum spanning tree for the given graph is drawn below:
MST = {(0, 1), (0, 3), (1, 2), (1, 4)}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
//Function to find sum of weights of edges of the Minimum Spanning Tree.
int spanningTree(int V, vector < vector < int >> adj[]) {
priority_queue < pair < int, int > ,
vector < pair < int, int > > , greater < pair < int, int >>> pq;
vector < int > vis(V, 0);
// {wt, node}
pq.push({
0,
0
});
int sum = 0;
while (!pq.empty()) {
auto it = pq.top();
pq.pop();
int node = it.second;
int wt = it.first;
if (vis[node] == 1) continue;
// add it to the mst
vis[node] = 1;
sum += wt;
for (auto it: adj[node]) {
int adjNode = it[0];
int edW = it[1];
if (!vis[adjNode]) {
pq.push({
edW,
adjNode
});
}
}
}
return sum;
}
};
int main() {
int V = 5;
vector<vector<int>> edges = {{0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}};
vector < vector < int >> adj[V];
for (auto it: edges) {
vector < int > tmp(2);
tmp[0] = it[1];
tmp[1] = it[2];
adj[it[0]].push_back(tmp);
tmp[0] = it[0];
tmp[1] = it[2];
adj[it[1]].push_back(tmp);
}
Solution obj;
int sum = obj.spanningTree(V, adj);
cout << "The sum of all the edge weights: " << sum << endl;
return 0;
}
The intuition of this algorithm is the greedy technique used for every node. If we carefully observe, for every node, we are greedily selecting its unvisited adjacent node with the minimum edge weight(as the priority queue here is a min-heap and the topmost element is the node with the minimum edge weight). Doing so for every node, we can get the sum of all the edge weights of the minimum spanning tree and the spanning tree itself(if we wish to) as well.
The Minimum Spanning Tree (MST) is a powerful concept in graph theory, with wide-ranging applications in real-world optimization problems. From designing cost-effective networks like electrical grids and telecommunication systems to minimizing distances in transportation networks, MST helps find the most efficient way to connect components while reducing total costs. Its practical importance makes MST algorithms like Kruskal's and Prim's essential tools in both academic and industrial settings.
For anyone looking to deepen their understanding of algorithms or improve their problem-solving skills, implementing MST algorithms is a great start. Platforms like HackerRank, Codeforces, and LeetCode offer numerous MST-related challenges that provide a hands-on way to apply these concepts and develop programming proficiency.
Challenge yourself to solve MST problems and explore how optimization can make complex systems more efficient!
Don’t worry, we don’t spam!