Hey everyone! Welcome back to another day of problem-solving. It's day 44, and I'm still going strong on my quest for consistency. Today, We will be solving a problem using Kruskal's Algorithm.
A prerequisite to solving this would be knowing about disjoint data sets.
I suggest watching this video. I will be writing down some explanation for the same but we will primarily focus on the problem.
Question: Minimum Spanning Tree
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 1:
Input:
- 3 3
- 0 1 5
- 1 2 3
- 0 2 1
Output : 4
Intuition and Breakdown:
Let's start by understanding what an MST or what a Minimum Spanning Tree is:
Minimum Spanning Tree (MST) is a subgraph of an undirected weighted graph that connects all the vertices together with the minimum possible total edge weight.
To put it basically we need to have all the nodes in one single tree minimizing the total edgeWeight and each node should be able to reach every other node through some path.
What is a Disjoint Set?
A disjoint set, also known as a union-find data structure, is a data structure that keeps track of a collection of disjoint (non-overlapping) sets. It provides efficient operations to determine whether elements are in the same set and to merge sets together.
It has two functions: Find Parent and UnionByRank/Size.
As the name suggests if given a node it will tell it's parent in the disjoint data set.
When we do a union of two nodes, the nodes with less rank/less size joins the node with higher rank/size.
We also do path compression and instead of storing parent we actually store the super parent because that is what it actually is.
A super parent is basically a parent which is itself's parent and it has nothing above it go to.
Application being : If two nodes don't have the same superParent in a disjoint set, they are in different componenents yet.
What is path compression?
Path Compression: Path compression is an optimization technique used in disjoint set data structures. It aims to reduce the height of the tree representing each set during the findUPar operation. By updating the parent of each traversed vertex to the ultimate parent, subsequent findUPar operations on the same set can be performed faster. Path compression ensures that the tree representing each set becomes almost flat, leading to improved performance.
Getting back to the question, we will be using disjoint data set to find our MST.
Algorithm Analysis:
First, we define a
DisjointSet
class to represent the disjoint set data structure. It initializes the parent, rank, and size arrays for each vertex. ThefindUPar
function is used to find the ultimate parent (representative) of a vertex using path compression. TheunionBySize
functions perform the union operation based on the size of the sets.To find the MST, we have a
spanningTree
function that takes the number of verticesV
and the adjacency list representation of the graphadj[]
. We start by creating a vector edges to store all the edges of the graph along with their weights. These edges are sorted in non-decreasing order of weights.Then, for each edge in the sorted order, we check if the vertices u and v belong to different sets using the
findUPar
function. If they are in different sets, it means that adding this edge to the MST will not form a cycle. So, we add the weight of the edge tomstWt
and perform the union operation usingunionBySize
to merge the sets containing u and v.
Code:
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 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[])
{
//making edges for applying disjoint set
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}});
}
}
sort(edges.begin(),edges.end());
int mstWt = 0;
DisjointSet ds(V);
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;
}
};
Complexity Analysis:
Time: O(ElogE) + O(E*4alpha*2)
Space: O(N)
Thanks for reading. Feedback is highly appreciated!
Top comments (0)