Kruskal's Algorithm - MST

Problem

Given a weighted, undirected, and connected graph with V vertices and E edges, the task is to find the sum of the weights of the edges in the Minimum Spanning Tree (MST) of the graph using Kruskal's Algorithm. The graph is represented as an edge list edges[][], where edges[i] = [u, v, w] denotes an undirected edge between u and v with weight w. (link)

Input: V = 3, E = 3, edges[][] = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]

Output: 4
Explanation:

The Spanning Tree resulting in a weight of 4 is shown above.

Input: V = 2, E = 1, edges = [[0, 1, 5]]

Output: 5 
Explanation: Only one Spanning Tree is possible which has a weight of 5.

**Constraints:
**2 ≤ V ≤ 1000
V-1 ≤ E ≤ (V*(V-1))/2
1 ≤ w ≤ 1000
The graph is connected and doesn't contain self-loops & multiple edges

Solution

Disjoint Set

1. Sort the Edges: Arrange all the edges in ascending order based on their weights.

2. Initialize Disjoint Sets: Create a disjoint set for each vertex to keep track of connected components.

3. Iterate Over Edges: Go through the sorted edges one by one.

4. Check for parents: If these 2 vertices belong to a different ultimate parent then add it to the disjoint set.

5. Update MST Weight: Add the weight of the edge to the total weight of the MST.

Time - O(E) + O(E log E) + O(E)

Space - O(E)

Disjoint set - O(4 x alpha)

class Solution {
    static int kruskalsMST(int V, int[][] edges) {

        List<Edge> edgeObjList = new ArrayList<>();
        for(int[] edge : edges){
            Edge edgeObj = new Edge(edge[2], edge[0], edge[1]);
            edgeObjList.add(edgeObj);
        }

        Collections.sort(edgeObjList);

        int mstSum = 0;

        DisjointSet ds = new DisjointSet(V);

        for(Edge edgeObj : edgeObjList){
            int u = edgeObj.u;
            int v = edgeObj.v;
            int wt = edgeObj.wt;

            if(ds.findParent(u) != ds.findParent(v)){
                ds.unionByRank(u,v);
                mstSum += wt;
            }
        }

        return mstSum;
    }
}


class Edge implements Comparable<Edge>{
    int wt;
    int u;
    int v;

    public Edge(int wt, int u, int v){
        this.wt = wt;
        this.u = u;
        this.v = v;
    }

    public int compareTo(Edge compareEdge){
        return this.wt - compareEdge.wt;
    }
}

class DisjointSet{
    int[] parent;
    int[] size;
    int[] rank;

    public DisjointSet(int n){
        this.parent = new int[n+1];
        this.size = new int[n+1];
        this.rank = new int[n+1];

        for(int i=0; i<n+1; i++){
            parent[i] = i;
        }
    }

    public int findParent(int u){

        if(parent[u]==u) return u;

        parent[u] = findParent(parent[u]);

        return parent[u];
    }

    public void unionBySize(int x, int y){

        int u = findParent(x);
        int v = findParent(y);

        if(u==v) return;

        if(size[u] < size[v]){
            parent[u] = v;
            size[v] += size[u];
        }
        else{
            parent[v] = u;
            size[u] += size[v];
        }

    }

    public void unionByRank(int x, int y){

        int u = findParent(x);
        int v = findParent(y);

        if(u==v) return;


        if(rank[u] < rank[v]){
            parent[u] = v;
        }
        else if(rank[u] > rank[v]){
            parent[v] = u;
        }
        else{
            parent[u] = v;
            rank[u] += 1;
        }
    }
}