Minimum Spanning Tree: Kruskal's Algorithm

Share

Given a weighted undirected graph, find the minimum spanning tree (MST) using Kruskal's algorithm. Return the total weight of the MST.

Example 1
Input: n=4, edges=[[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]] → MST weight=19
Example 2
Input: n=3, edges=[[0,1,1],[1,2,2],[0,2,4]] → MST weight=3

Solution Approach

Sort edges by weight. Use Union-Find: add an edge to MST if it connects two different components.

  • Sort edges by weight (ascending).
  • For each edge (u,v,w): if find(u) != find(v): add to MST (totalWeight += w), union(u,v).
  • Stop when MST has n-1 edges.
Java
import java.util.*;

class Solution {
    int[] parent, rank;

    public int kruskalMST(int n, int[][] edges) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        Arrays.sort(edges, (a,b)->a[2]-b[2]);
        int total = 0, edgesUsed = 0;
        for (int[] e : edges) {
            if (edgesUsed == n-1) break;
            int pu=find(e[0]), pv=find(e[1]);
            if (pu != pv) {
                if (rank[pu] < rank[pv]) parent[pu]=pv;
                else if (rank[pu] > rank[pv]) parent[pv]=pu;
                else { parent[pv]=pu; rank[pu]++; }
                total += e[2]; edgesUsed++;
            }
        }
        return total;
    }
    private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
}
  • Time Complexity: O(E log E)
  • Space Complexity: O(V)