Kruskal's Algorithm for MST with DSU

1. What is a Minimum Spanning Tree (MST)?

Before we dive into the algorithm, let's clarify what we're trying to build. For a given connected, undirected, and weighted graph, a Spanning Tree is a subgraph that:

• Connects all the vertices together (it's "spanning").
• Has no cycles (it's a "tree").
• For a graph with V vertices, it will always have exactly V-1 edges.

A graph can have many different spanning trees. The Minimum Spanning Tree (MST) is the one where the sum of the weights of all its edges is as small as possible.

2. Kruskal's Algorithm: A Greedy Approach

Kruskal's algorithm finds the MST using a simple but powerful greedy strategy. This means at every step, it makes the locally optimal choice, which, in this case, is to pick the smallest available edge. The core idea relies on one key insight: if we always add the cheapest possible edge that doesn't create a cycle, we will end up with an MST.

The algorithm can be broken down into three main steps.

As the video highlights, the crucial part is knowing whether adding an edge will form a cycle. This is where the DSU data structure you learned in the previous lesson comes in. If two vertices of an edge are already in the same set (i.e., their find() operation returns the same representative), it means there is already a path between them. Adding the new edge would create a cycle. DSU allows us to check this in nearly constant time.

3. A Step-by-Step Walkthrough

Let's visualize the algorithm's execution. We start with each vertex in its own component. We then iterate through all graph edges, sorted by weight, and add an edge to our MST only if it connects two previously disconnected components.

To see a dynamic walkthrough, the following video explains the process clearly, connecting each step back to the DSU operations.

4. Java Implementation

Now, let's put all the pieces together in Java. The implementation requires two main parts:

1. The UnionFind (or DSU) class from our previous lesson.
2. The main logic for Kruskal's algorithm, which sorts the edges and uses the UnionFind object to build the MST.

For your convenience, here is the UnionFind class implementation we discussed previously, using union by size and path compression.

// DSU class from the previous lesson
class UnionFind {
    private int[] parent;
    private int[] size;

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

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by size
            if (size[rootI] < size[rootJ]) {
                parent[rootI] = rootJ;
                size[rootJ] += size[rootI];
            } else {
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
        }
    }
}

With the UnionFind class ready, we can implement Kruskal's algorithm. A common way to represent edges in competitive programming is with a simple array or list, where each element represents an edge [source, destination, weight].

The following video demonstrates the full coding process in Java.

Here is a complete, runnable Java code snippet that finds the total weight of the MST. This version is similar to what you'd write in an interview or coding competition.

import java.util.Arrays;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.List;

class KruskalAlgorithm {

    // Edge class to store source, destination, and weight
    static class Edge {
        int src, dest, weight;
        Edge(int s, int d, int w) {
            this.src = s;
            this.dest = d;
            this.weight = w;
        }
    }

    public static int kruskalsMST(int V, List<Edge> edges) {
        // 1. Sort all edges in non-decreasing order of their weight.
        edges.sort(Comparator.comparingInt(e -> e.weight));
        
        // Initialize DSU
        UnionFind dsu = new UnionFind(V);
        
        int mstWeight = 0;
        int edgesInMST = 0;
        List<Edge> mstEdges = new ArrayList<>(); // To store the edges of the MST

        // 2. Iterate through all sorted edges
        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;
            
            // 3. Check if including this edge forms a cycle
            if (dsu.find(u) != dsu.find(v)) {
                // If not, include it in the MST
                dsu.union(u, v);
                mstWeight += weight;
                mstEdges.add(edge);
                edgesInMST++;
                
                // An MST has V-1 edges, so we can stop early
                if (edgesInMST == V - 1) {
                    break;
                }
            }
        }
        
        System.out.println("Edges in the MST:");
        for(Edge e : mstEdges) {
            System.out.println(e.src + " - " + e.dest + " : " + e.weight);
        }

        return mstWeight;
    }

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

        int result = kruskalsMST(V, edges);
        System.out.println("Minimum Cost of Spanning Tree: " + result);
    }
}

5. Complexity Analysis

Understanding the performance of an algorithm is critical for interviews.

• Time Complexity: The most expensive operation is sorting the edges, which takes $O(E\log E)$ time, where $E$ is the number of edges. The loop iterates through $E$ edges, and each DSU operation (find, union) takes nearly constant time, $O(\alpha (V))$, where $V$ is the number of vertices.
  Thus, the total time is dominated by the sort: $O(E\log E)$ or $O(E\log V)$, since $\log E$ is proportional to $\log V$ in most graphs.

• Space Complexity: We need space to store the edges, which is $O(E)$, and space for the DSU data structure, which is $O(V)$. Therefore, the total space complexity is $O(V+E)$.

Conclusion

Congratulations! You have now implemented Kruskal's algorithm, a fundamental greedy algorithm for finding a Minimum Spanning Tree. You've also seen a practical, powerful application of the DSU data structure.

Key Takeaways:

• Kruskal's algorithm builds an MST by greedily adding the smallest-weighted edges that do not form a cycle.
• The algorithm's efficiency hinges on two key components: sorting all edges by weight and using a DSU for near-constant time cycle detection.
• The time complexity is dominated by the sorting step, resulting in $O(E\log E)$.
• The space complexity is $O(V+E)$ to store the graph's vertices and edges.

Preview of the Next Lesson:
Kruskal's algorithm is one of two famous greedy algorithms for finding an MST. The other is Prim's algorithm. In the next lesson, you will learn how to implement Prim's algorithm, which takes a different greedy approach: instead of connecting components, it grows a single tree, one vertex at a time. This will give you another powerful tool for solving MST problems.