Kruskal's MST Implementation: Union-Find in Practice with Step-by-Step Examples

Kruskal’s Algorithm is one of the most popular methods to find the Minimum Spanning Tree (MST) of a weighted graph. An MST connects all vertices of a graph with the minimum possible total edge weight and avoids cycles. The core of Kruskal’s algorithm lies in sorting the edges and efficiently checking whether adding an edge would create a cycle. For this, we use the Union-Find (Disjoint Set Union – DSU) data structure.

In this article, we will break down Kruskal’s Algorithm step by step, visually demonstrate the process, and implement it in Python using Union-Find.

Table of Contents

When to Use Kruskal’s Algorithm?

When the graph is sparse (fewer edges compared to number of vertices).
If the edges can be easily sorted (complexity reduction potential).
When you need to guarantee the smallest total weight for connectivity.

Understanding Kruskal’s Algorithm

Kruskal’s works by always choosing the smallest weight edge that doesn’t form a cycle with the already chosen edges. This continues until we have exactly (V-1) edges for a graph with V vertices.

The Union-Find Data Structure

Union-Find helps in efficiently answering the question: “Do these two vertices belong to the same connected component?” It has two main operations:

find(x) → Finds the root/representative of a set containing x.
union(x, y) → Connects two sets if they are not already connected.

We use two optimizations for efficiency:

Path Compression in find → Makes the tree flat by pointing nodes directly to root.
Union by Rank/Size → Always attach smaller tree under the root of the larger one.

Step-by-Step Example

Let’s consider the following weighted graph:

Steps of Kruskal’s algorithm on this graph:

Sort edges by weight: (A-B:1), (B-C:2), (C-D:3), (B-D:4), (A-C:5).
Pick A-B (weight 1) → no cycle → add to MST.
Pick B-C (weight 2) → no cycle → add to MST.
Pick C-D (weight 3) → no cycle → add to MST.
Now MST contains 3 edges for 4 vertices ⇒ MST complete.

Final MST Edges: (A-B, B-C, C-D) with total weight = 6.

Python Implementation of Kruskal’s Algorithm with Union-Find


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            if self.rank[rootU] < self.rank[rootV]:
                self.parent[rootU] = rootV
            elif self.rank[rootU] > self.rank[rootV]:
                self.parent[rootV] = rootU
            else:
                self.parent[rootV] = rootU
                self.rank[rootU] += 1
            return True
        return False

def kruskal(n, edges):
    # edges is a list of tuples (weight, u, v)
    uf = UnionFind(n)
    mst = []
    total_weight = 0

    edges.sort()
    for w, u, v in edges:
        if uf.union(u, v):  # only add if no cycle
            mst.append((u, v, w))
            total_weight += w
    return mst, total_weight

# Example Graph
edges = [
    (1, 0, 1), # A-B
    (5, 0, 2), # A-C
    (2, 1, 2), # B-C
    (4, 1, 3), # B-D
    (3, 2, 3)  # C-D
]

mst, weight = kruskal(4, edges)
print("MST edges:", mst)
print("Total weight:", weight)

Output:


MST edges: [(0, 1, 1), (1, 2, 2), (2, 3, 3)]
Total weight: 6

Complexity Analysis

Sorting edges: O(E log E)
Union-Find operations: ~O(α(V)), where α is the Inverse Ackermann function (nearly constant)
Total Complexity: O(E log E)

Interactive Exercise

Try modifying the edges or weights in the Python implementation above. Remove one edge or increase a weight — observe how the MST changes. This hands-on practice helps in understanding how cycles are avoided and why cheaper edges are prioritized.

Conclusion

Kruskal’s MST algorithm, combined with Union-Find, provides a highly efficient way of solving graph connectivity problems. It is widely used in network design, clustering, and spanning tree-related optimizations. By understanding the edge sorting and disjoint set operations, one can implement it effectively in any programming language.

Now that you know Kruskal’s algorithm, you are ready to tackle real-world applications of spanning trees, from designing communication networks to optimizing road connections!