G-47. Kruskal's Algorithm - Minimum Spanning Tree - C++ and Java

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph. By leveraging the Disjoint Set Union (DSU) data structure, Kruskal's algorithm efficiently picks the lowest-weight edges while preventing cycles, ensuring all vertices are connected with the minimum possible total edge weight.

1. Why Do We Need Kruskal's Algorithm? (Problem Statement)

• Status Quo: When given a weighted, undirected graph, we often need to connect all $V$ vertices using $V - 1$ edges such that the total sum of edge weights is minimized, and there are no cycles. This structure is called a Minimum Spanning Tree (MST).
• Alternative Approaches: We can use Prim's Algorithm (which grows the MST vertex by vertex using a priority queue). However, Kruskal's algorithm takes a different philosophy: it focuses entirely on sorting and selecting edges rather than growing from a starting vertex.
• The Core Challenge: How do we efficiently check if adding an edge between two nodes will create a cycle without running an expensive graph traversal (like BFS/DFS) every single time?
• The Solution: Combine a sorting step (to always process the cheapest available edge) with a Disjoint Set data structure (to instantly check connectivity and merge components in near-constant time).

2. Core Mental Model: The Social Circle Analogy

Real-Life Analogy: Imagine people at a party divided into separate independent friendship groups (components).

• Each person has an individual "boss" or ultimate parent representing their group.
• When considering a new friendship bridge (edge) between Person $U$ and Person $V$, we ask: "Do you both share the same ultimate boss?"
• If Yes, they are already part of the same social circle. Adding this bridge would create a redundant loop (cycle), so we discard it.
• If No, they belong to separate circles. We safely accept the bridge and union (merge) their social circles together under one unified boss.

3. Step-by-Step Evolution of Kruskal's Algorithm

To find the Minimum Spanning Tree for a graph with $V$ vertices and $E$ edges, follow this exact workflow:

1. Extract and Convert: If given an adjacency list, extract all unique undirected edges into an edge list format containing (weight, u, v).
2. Sort the Edges: Sort all extracted edges in non-decreasing order of their weights (lightest to heaviest).
3. Initialize Disjoint Set: Create a Disjoint Set data structure for all $V$ vertices where every node is initially its own parent (size 1).
4. Iterate & Evaluate: Traverse through the sorted edges one by one:
   • Find the ultimate parents of both nodes $U$ and $V$ using the Disjoint Set.
   • If they have different ultimate parents, include the edge in the MST, add its weight to the total MST weight, and perform a Union of their components.
   • If they have the same ultimate parent, discard the edge (as it would form a cycle).
5. Termination: Stop once we have successfully added $V - 1$ edges, or after checking all sorted edges.

4. Visualizing the Edge Selection Process

Consider a graph with 6 nodes ($1$ to $6$) and multiple weighted edges. After sorting all edges by weight, our algorithm processes them sequentially:

Detailed dry run on sample graph edges:

• Edge (1, 4) with weight 1: Parents are 1 and 4. Different components $\rightarrow$ Accept. Add to MST.
• Edge (1, 2) with weight 2: Parents are 1 and 2. Different components $\rightarrow$ Accept. Add to MST.
• Edge (2, 3) with weight 3: Parents are 2 and 3. Different components $\rightarrow$ Accept. Add to MST.
• Edge (2, 4) with weight 4: Parents are both connected to component rooted at 1. Same component $\rightarrow$ Discard (prevents cycle).
• Edge (1, 5) with weight ...: Different components $\rightarrow$ Accept.
• Edge (2, 6) with weight 7: Different components $\rightarrow$ Accept.

Total accumulated weight = 1 + 2 + 3 + ... = 17.

5. C++ Implementation

#class DisjointSet {
    vector<int> rank, parent, size;
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUltimateParent(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUltimateParent(parent[node]); // Path compression
    }

    void unionByRank(int u, int v) {
        int ulp_u = findUltimateParent(u);
        int ulp_v = findUltimateParent(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        } else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        } else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUltimateParent(u);
        int ulp_v = findUltimateParent(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:
    int kruskalsMST(int V, vector<vector<int>> adj[]) {
        // Step 1: Extract all edges from adjacency list -> format: {weight, {u, v}}
        vector<pair<int, pair<int, int>>> edges;
        for (int i = 0; i < V; i++) {
            for (auto it : adj[i]) {
                int adjNode = it[0];
                int weight = it[1];
                int node = i;
                edges.push_back({weight, {node, adjNode}});
            }
        }

        // Step 2: Sort edges according to weight
        sort(edges.begin(), edges.end());

        // Step 3: Initialize Disjoint Set
        DisjointSet ds(V);
        int mstWeight = 0;

        // Step 4: Iterate through sorted edges
        for (auto it : edges) {
            int weight = it.first;
            int u = it.second.first;
            int v = it.second.second;

            // If u and v belong to different components, include in MST
            if (ds.findUltimateParent(u) != ds.findUltimateParent(v)) {
                mstWeight += weight;
                ds.unionBySize(u, v);
            }
        }

        return mstWeight;
    }
};

6. Java Implementation

import java.util.*;

class DisjointSet {
    List<Integer> rank = new ArrayList<>();
    List<Integer> parent = new ArrayList<>();
    List<Integer> size = new ArrayList<>();

    public DisjointSet(int n) {
        for (int i = 0; i <= n; i++) {
            rank.add(0);
            parent.add(i);
            size.add(1);
        }
    }

    public int findUltimateParent(int node) {
        if (node == parent.get(node)) {
            return node;
        }
        int ulp = findUltimateParent(parent.get(node));
        parent.set(node, ulp);
        return parent.get(node);
    }

    public void unionByRank(int u, int v) {
        int ulp_u = findUltimateParent(u);
        int ulp_v = findUltimateParent(v);
        if (ulp_u == ulp_v) return;
        if (rank.get(ulp_u) < rank.get(ulp_v)) {
            parent.set(ulp_u, ulp_v);
        } else if (rank.get(ulp_v) < rank.get(ulp_u)) {
            parent.set(ulp_v, ulp_u);
        } else {
            parent.set(ulp_v, ulp_u);
            int rankU = rank.get(ulp_u);
            rank.set(ulp_u, rankU + 1);
        }
    }

    public void unionBySize(int u, int v) {
        int ulp_u = findUltimateParent(u);
        int ulp_v = findUltimateParent(v);
        if (ulp_u == ulp_v) return;
        if (size.get(ulp_u) < size.get(ulp_v)) {
            parent.set(ulp_u, ulp_v);
            size.set(ulp_v, size.get(ulp_v) + size.get(ulp_u));
        } else {
            parent.set(ulp_v, ulp_u);
            size.set(ulp_u, size.get(ulp_u) + size.get(ulp_v));
        }
    }
}

class Solution {
    // Edge class to store weight, u, and v
    static class Edge implements Comparable<Edge> {
        int weight, u, v;

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

        @Override
        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    }

    public int kruskalsMST(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj) {
        // Step 1: Extract all edges
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < adj.get(i).size(); j++) {
                int adjNode = adj.get(i).get(j).get(0);
                int weight = adj.get(i).get(j).get(1);
                edges.add(new Edge(weight, i, adjNode));
            }
        }

        // Step 2: Sort edges by weight
        Collections.sort(edges);

        // Step 3: Initialize Disjoint Set
        DisjointSet ds = new DisjointSet(V);
        int mstWeight = 0;

        // Step 4: Iterate and process edges
        for (Edge edge : edges) {
            int u = edge.u;
            int v = edge.v;
            int weight = edge.weight;

            if (ds.findUltimateParent(u) != ds.findUltimateParent(v)) {
                mstWeight += weight;
                ds.unionBySize(u, v);
            }
        }

        return mstWeight;
    }
}

7. Comparative Analysis: Kruskal's vs. Prim's Algorithm

8. Complexity Analysis

• Time Complexity:
  • Edge Extraction: $O(V + E)$ to iterate through the adjacency list and store all edges.
  • Sorting Edges: $O(E \log E)$ where $E$ is the total number of edges. Since $E \le V^2$, this can also be written as $O(E \log V)$.
  • DSU Operations: For each of the $E$ edges, we perform findUltimateParent and union operations, which run in nearly constant time $O(4\alpha) \approx O(1)$ using path compression and union by rank/size.
  • Total Time Complexity: $O(M \log M + M \cdot 4\alpha)$ (where $M$ represents the number of edges).
• Space Complexity:
  • Edge Storage: $O(E)$ to store all graph edges in an edge list.
  • Disjoint Set Structure: $O(V)$ auxiliary space for parent, size / rank arrays.
  • Total Space Complexity: $O(E + V)$.

9. Summary and Key Takeaways

• Greedy Edge Selection: Kruskal's algorithm always prioritizes the locally smallest available edge weight to construct the global Minimum Spanning Tree.
• Prerequisite Data Structure: Mastery of the Disjoint Set Union (DSU) data structure—specifically findUltimateParent with path compression and unionBySize/unionByRank—is mandatory to understand Kruskal's implementation.
• Cycle Prevention: DSU allows instantaneous $O(1)$ verification of whether two vertices belong to the same connected component, cleanly avoiding cycles without graph traversals.
• Bi-Directional Edge Handling: Undirected graphs store edges twice in adjacency lists; DSU naturally handles and discards redundant duplicate edges without requiring manual pre-filtering.
• Sorting is Key: The entire algorithm hinges on sorting the edge list by weight in ascending order before evaluating components.
• Production Efficiency: Kruskal's algorithm is exceptionally performant and straightforward to implement, making it a staple for solving network design, clustering, and routing optimization problems.