DAY 46 - Minimum Spanning Tree

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. The findUPar function is used to find the ultimate parent (representative) of a vertex using path compression. The unionBySize 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 vertices V and the adjacency list representation of the graph adj[]. 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 to mstWt and perform the union operation using unionBySize 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!