Kruskal's Algorithm: A Hands-On Visual Guide with Python

The Story That Explains Kruskal's Algorithm

Kruskal's algorithm finds the Minimum Spanning Tree (MST) of a weighted, undirected graph: the cheapest set of edges connecting all vertices with no cycles. Where Prim's grows a single tree outward from one vertex, Kruskal's is edge-centric — it sorts all edges once and greedily merges separate clusters into one, using a clever data structure called Union-Find to detect cycles instantly.

The Foundation — Spanning Trees & the Cycle Rule

A spanning tree touches every one of the V vertices, stays connected, and has no cycle — so it always contains exactly V − 1 edges. The minimum spanning tree is the spanning tree whose edge weights sum to the smallest possible total. Kruskal's relies on two twin rules of MST theory.

The Engine Room — Union-Find (Disjoint Set Union)

The whole algorithm hinges on answering one question fast, millions of times if needed: "are these two vertices already connected?" The Union-Find structure (also called Disjoint Set Union, or DSU) does exactly this in near-constant time.

The Algorithm in Five Steps

Hands-On: Watch Every Line of Code Build the Tree

This is the heart of the tutorial. The graph on the left colours each vertex by its Union-Find component, and the Python on the right is wired to it. Press Play (or step manually) and the highlighted line of code is the task happening on the canvas: when sorted(edges) runs, the edge strip orders itself; when find runs, the edge under consideration pulses; a union turns the edge green and recolours the absorbed component into the growing blue tree; a cycle edge flashes red and is discarded.

Python Implementation

Full Version — Union-Find with Path Compression & Union by Rank

This is the production-quality implementation. The two helper functions are the Union-Find engine; kruskal itself is just a sorted loop over the edges.

def find(parent, x):
    while parent[x] != x:               # walk up to the root of x's set
        parent[x] = parent[parent[x]]   # path compression: flatten the tree
        x = parent[x]
    return x

def union(parent, rank, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return False                    # same set -> this edge is a cycle
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra                 # attach the shorter tree...
    parent[rb] = ra                     # ...under the taller one
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True

def kruskal(nodes, edges):
    parent = {v: v for v in nodes}      # every vertex is its own set
    rank   = {v: 0 for v in nodes}
    mst, total = [], 0
    for w, u, v in sorted(edges):       # greedily scan edges, lightest first
        if union(parent, rank, u, v):   # keep only edges that link two sets
            mst.append((u, v, w))
            total += w
            if len(mst) == len(nodes) - 1:
                break                   # V-1 edges -> spanning tree done
    return mst, total

Running It on Our Six-Village Graph

Note that each edge is stored as (weight, u, v) so that Python's sorted() orders by weight first — the only thing Kruskal needs.

nodes = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [
    (1, 'A', 'B'), (2, 'C', 'D'), (3, 'B', 'C'), (4, 'A', 'C'),
    (5, 'D', 'E'), (6, 'E', 'F'), (7, 'B', 'E'), (8, 'A', 'F'),
]

tree, cost = kruskal(nodes, edges)
for u, v, w in tree:
    print(f"{u} -- {v}  (weight {w})")
print("Total MST cost:", cost)

The Run, Traced Step by Step

Here is exactly what the animation does, written out. Edges are processed in sorted order, and the Union-Find check decides each one's fate.

Time & Space Complexity

Benefits of Kruskal's Algorithm

Real-World Use Cases

Kruskal vs Prim — Side by Side

Golden Rules