Problem Statement
Given a weighted, undirected, and connected graph with V vertices numbered from 0 to V-1 and E edges.
The ith edge is represented by [a(i), b(i), w(i)], where a(i) and b(i) denotes the endpoint of the edge and the w(i) denotes the weight of the edge.
Find the sum of the weights of the edges in the Minimum Spanning Tree (MST) of the graph.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Examples
Example 1:
Input: V = 4, edges = [
[0, 1, 1],
[1, 2, 2],
[2, 3, 3],
[0, 3, 4]
]
Output: 6
Explanation: Edges included in the MST:
[0, 1, 1] with weight 1
[1, 2, 2] with weight 2
[2, 3, 3] with weight 3
The total weight of the MST is 1 + 2 + 3 = 6. These edges form a spanning tree that connects all vertices (0, 1, 2, 3) with the minimum possible total edge weight satisfying the MST properties.Example 2:
Input: V = 3, edges = [
[0, 1, 5],
[1, 2, 10],
[2, 0, 15]
]
Output: 15
Explanation:
Edges included in the MST:
[0, 1, 5] with weight 5.
[1, 2, 10] with weight 10.
The total weight of the MST is 5 + 10 = 15.Different Approaches
1️⃣ Prim's Algorithm
Intuition:
The minimum spanning tree consists of edges having minimum possible edge weight that are connecting all the nodes. So, a greedy approach can be followed where all the edges are considered from a node and the minimum edge is considered connecting that node. This way, it ensures that once all the nodes are visited, the edges that are taken into the consideration form a minimum spanning tree.
This is the principle behind the Prim's Algorithm to find the minimum spanning tree for a given graph.
Algorithm:
- Start with any node as the initial node in the MST. Set its key value to 0 and all other nodes' key values to infinity.
- Select the node with the minimum key value that is not yet included in the MST. Add this node to the MST.
- Update the key values of its adjacent nodes to the edge weights if the edge weight is smaller than the current key value.
- Repeat the process until all nodes are included in the MST.
- Once all the nodes are included, the MST is complete
Understanding:
Since, from every node, the minimum edge will be considered for the MST every time, the best data structure to use here will be the Minimum heap data structure, which will store a pair: {edge, node}.
Approach:
- A minimum priority queue (min-heap) is used to keep track of the edges based on their weights. A visited array is used to mark nodes that have been included in the MST.
- An arbitrary initial node is pushed into the priority queue with an edge weight of 0. While the priority queue is not empty, extract the edge with the minimum weight.
- If the node connected by this edge is already visited, skip it. Otherwise, mark the node as visited and add the edge weight to the MST sum.
- Traverse all adjacent edges of the current node. For each adjacent node that is not visited, push the edge into the priority queue.
- The process continues until all nodes are included in the MST. The final sum of the weights of the edges in the MST is returned.
Code:
#include <bits/stdc++.h>
using namespace std;
/* Define P as a shorthand for
the pair<int, pair<int,int>> type */
#define P pair<int,int>
class Solution{
public:
// Function to get the sum of weights of edges in MST
int spanningTree(int V, vector<vector<int>> adj[]) {
// Min-Heap to store pair of {edge, node}
priority_queue <P, vector<P>, greater<P>> pq;
// Visited array
vector<int> visited(V, 0);
// Push any arbitrary initial node
pq.push({0,0});
// To store the weight of MST
int sum = 0;
// Until the priority queue is not empty
while(!pq.empty()) {
// Get the pair with minimum edge
auto p = pq.top();
pq.pop();
int node = p.second; // Get the node
int wt = p.first; // Get the edge weight
/* If the node is already visited,
skip the iteration */
if(visited[node] == 1) continue;
// Otherwise, mark the node as visited
visited[node] = 1;
// Update the weight of MST
sum += wt;
// Traverse all the edges of the node
for(auto it : adj[node]) {
// Get the adjacent node
int adjNode = it[0];
// Get the edge weight
int edgeWt = it[1];
/* Add the pair to min-heap if
the node is not visited already */
if(visited[adjNode] == 0) {
pq.push({edgeWt, adjNode});
}
}
}
// Return the weight of MST
return sum;
}
};
int main() {
int V = 4;
vector<vector<int>> edges = {
{0, 1, 1},
{1, 2, 2},
{2, 3, 3},
{0, 3, 4}
};
// Forming the adjacency list from edges
vector<vector<int>> adj[4];
for(auto it : edges) {
int u = it[0];
int v = it[1];
int wt = it[2];
adj[u].push_back({v, wt});
adj[v].push_back({u, wt});
}
// Creating instance of Solution class
Solution sol;
/* Function call to get the sum
of weights of edges in MST */
int ans = sol.spanningTree(V, adj);
cout << "The sum of weights of edges in MST is: " << ans;
return 0;
}Complexity Analysis:
- Time Complexity:
O(ElogE)(where E is the number of edges in the graph)
In the worst case, the min-heap will store all the E edges, and insertion operation on the min-heap takes O(logE) time taking overall O(ElogE) time. - Space Complexity:
O(E + V)(where V is the number of nodes in the graph)
The min-heap will store all edges in worst-case taking O(E) space and the visited array takes O(V) space.
2️⃣ Kruskal's Algorithm
Intuition:
Since, the minimum spanning tree consists of edges connecting all nodes with the minimum total weight, a greedy approach can be followed where the edges with the smallest edge weight can be added to the MST set one by one till all the nodes are not added to the MST.
Algorithm:
- Sort all the edges in ascending order based on their weights. Initialize the total weight sum to 0.
- Initialize a data structure to keep track of connected components (e.g., union-find).
- Iterate through the sorted edges:
- For each edge, check if the vertices it connects are in different components.
- If they are in different components, add the edge's weight to the total weight sum and unite the components.
- Continue this process until all vertices are connected or all edges have been processed.
Approach:
- A Disjoint Set class is created to manage the union-find operations. This class supports union by rank and union by size to efficiently manage the merging of sets.
- All edges from the adjacency list representation of the graph are extracted and stored in a list, with each edge represented as a pair of its weight and the two vertices it connects.
- The list of edges is sorted in ascending order based on their weights. This ensures that the smallest edges are considered first, which is a key aspect of Kruskal's algorithm.
- A variable is initialized to keep track of the sum of the weights of the edges included in the MST.
- Iterate through the sorted list of edges. For each edge, check if the two vertices connected by the edge belong to different sets using the union-find structure. If they do, add the edge's weight to the MST sum and merge the sets containing these two vertices.
- After processing all edges, the sum of the weights of the edges in the MST is returned.
Code:
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
/* To store the ranks, parents and
sizes of different set of vertices */
vector<int> rank, parent, size;
public:
// Constructor
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;
}
}
// Function to find ultimate parent
int findUPar(int node) {
if (node == parent[node])
return node;
return parent[node] = findUPar(parent[node]);
}
// Function to implement union by rank
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]++;
}
}
// Function to implement union by size
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];
}
}
};
// Solution class
class Solution{
public:
// Function to get the sum of weights of edges in MST
int spanningTree(int V, vector<vector<int>> adj[]) {
// To store the edges
vector<pair<int, pair<int, int>>> edges;
// Getting all edges from adjacency list
for (int i = 0; i < V; i++) {
for (auto it : adj[i]) {
int v = it[0]; // Node v
int wt = it[1]; // edge weight
int u = i; // Node u
edges.push_back({wt, {u, v}});
}
}
// Creating a disjoint set of V vertices
DisjointSet ds(V);
// Sorting the edges based on their weights
sort(edges.begin(), edges.end());
// To store the sum of edges in MST
int sum = 0;
// Iterate on the edges
for (auto it : edges) {
int wt = it.first; // edge weight
int u = it.second.first; // First node
int v = it.second.second; // Second node
// Join the nodes if not in the same set
if (ds.findUPar(u) != ds.findUPar(v)) {
// Update the sum of edges in MST
sum += wt;
// Unite the nodes
ds.unionBySize(u, v);
}
}
// Return the computed sum
return sum;
}
};
int main() {
int V = 4;
vector<vector<int>> edges = {
{0, 1, 1},
{1, 2, 2},
{2, 3, 3},
{0, 3, 4}
};
// Forming the adjacency list from edges
vector<vector<int>> adj[4];
for(auto it : edges) {
int u = it[0];
int v = it[1];
int wt = it[2];
adj[u].push_back({v, wt});
adj[v].push_back({u, wt});
}
// Creating instance of Solution class
Solution sol;
/* Function call to get the sum
of weights of edges in MST */
int ans = sol.spanningTree(V, adj);
cout << "The sum of weights of edges in MST is: " << ans;
return 0;
}Complexity Analysis:
- Time Complexity:
O(V+E) + O(ElogE) + O(E*4α*2)(where V and E are the numbers of nodes and edges in the graph)- Extracting edges from adjacency list takes O(V+E) time.
- Sorting the edges takes O(ElogE) time.
- In the worst case, all the edges are iterated and added to the disjoint set. The find parent and union operation takes 4α time making overall time complexity as O(E*4α*2).
- Space Complexity:
O(V+E)- Storing the edges take O(E) space.
- The disjoint set on V vertices take O(V) space due to parent, rank/size arrays.