Kruskal's Algorithm

class UnionFind:
    """Union-Find (Disjoint Set) data structure with path compression and union by rank"""
    
    def __init__(self, n):
        self.parent = list(range(n))  # Each node is its own parent initially
        self.rank = [0] * n  # Rank for union by rank optimization
    
    def find(self, x):
        """Find the root of x with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        """Union two sets containing x and y"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False  # Already in same set
        
        # Union by rank: attach smaller tree under larger tree
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        return True


def kruskals_mst(n, edges):
    """
    Find Minimum Spanning Tree using Kruskal's Algorithm
    
    Args:
        n: Number of vertices (0 to n-1)
        edges: List of edges [(u, v, weight), ...]
    
    Returns:
        List of edges in MST: [(u, v, weight), ...]
    """
    # Step 1: Sort edges by weight
    edges.sort(key=lambda x: x[2])
    
    # Step 2: Initialize Union-Find
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    # Step 3: Process edges in sorted order
    for u, v, weight in edges:
        # If u and v are in different components (no cycle)
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
            
            # Stop when we have V-1 edges
            if len(mst) == n - 1:
                break
    
    return mst, total_weight


# Example Usage
n = 5  # 5 vertices (0 to 4)
edges = [
    (0, 1, 4),
    (0, 2, 2),
    (1, 2, 1),
    (1, 3, 5),
    (2, 3, 8),
    (2, 4, 10),
    (3, 4, 2)
]

mst, total_weight = kruskals_mst(n, edges)
print("MST Edges:", mst)
# Output: [(1, 2, 1), (0, 2, 2), (3, 4, 2), (1, 3, 5)]

print(f"Total MST Weight: {total_weight}")
# Output: Total MST Weight: 10

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest;
    long weight;

    public Edge(int src, int dest, long weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        int byWeight = Long.compare(this.weight, other.weight);
        if (byWeight != 0) return byWeight;
        int bySource = Integer.compare(this.src, other.src);
        return bySource != 0 ? bySource : Integer.compare(this.dest, other.dest);
    }
}

class UnionFind {
    int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    public boolean union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);

        if (rootI != rootJ) {
            if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            return true;
        }
        return false;
    }
}

public class Kruskals {
    public static void kruskalsMST(int V, List<Edge> edges) {
        Collections.sort(edges);
        UnionFind uf = new UnionFind(V);
        List<Edge> mst = new ArrayList<>();
        long totalWeight = 0L;

        for (Edge edge : edges) {
            if (uf.union(edge.src, edge.dest)) {
                mst.add(edge);
                totalWeight = Math.addExact(totalWeight, edge.weight);
                if (mst.size() == Math.max(0, V - 1)) break;
            }
        }

        System.out.println("MST Edges:");
        for (Edge edge : mst) {
            System.out.println("(" + edge.src + ", " + edge.dest + ", " + edge.weight + ")");
        }
        System.out.println("Total MST Weight: " + totalWeight);
        if (mst.size() != Math.max(0, V - 1)) {
            System.out.println("No MST: returned a minimum spanning forest");
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(0, 2, 2));
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(1, 3, 5));
        edges.add(new Edge(2, 3, 8));
        edges.add(new Edge(2, 4, 10));
        edges.add(new Edge(3, 4, 2));

        kruskalsMST(V, edges);
        // Output:
        // MST Edges:
        // (1, 2, 1)
        // (0, 2, 2)
        // (3, 4, 2)
        // (1, 3, 5)
        // Total MST Weight: 10
    }
}