Minimum Spanning Tree: Kruskal vs Prim Explained Deeply

Network infrastructure engineers don't debate Kruskal vs Prim at a whiteboard for fun — they debate it because the wrong choice can tank performance on a graph with a million edges. MST algorithms power cable laying, circuit board routing, cluster analysis in machine learning, image segmentation, and approximation algorithms for NP-hard problems like TSP. If you've ever wondered how Spotify groups similar songs or how Cisco routes OSPF traffic, MSTs are lurking in the background.

The core problem MST solves is deceptively simple: given a connected, weighted, undirected graph, find the subset of edges that keeps the graph connected, contains no cycle, and has the minimum possible total edge weight. That subset is always a tree (N nodes, N-1 edges). The real challenge is doing this efficiently at scale — a naive approach checking all spanning trees is factorial in complexity, which is completely unusable in production.

By the end of this article you'll understand not just how both algorithms work, but why they're correct (the cut property and cycle property of MSTs), when each one dominates the other in practice, how Union-Find with path compression makes Kruskal fly, how a priority queue shapes Prim's performance, and exactly what breaks in each algorithm when your graph has duplicate edge weights, disconnected components, or negative weights.

What is Minimum Spanning Tree? — Plain English

A Minimum Spanning Tree (MST) is a subset of edges in a connected, undirected, weighted graph that: (1) connects all nodes, (2) contains no cycles, and (3) has the minimum possible total edge weight.

Real-world analogy: a telephone company wants to lay cables connecting 10 cities. They want every city reachable from every other city, and they want to minimize the total cable length. The MST gives the exact set of cables to lay. Two classic algorithms solve MST: Kruskal's (sort edges, add cheapest that doesn't form a cycle) and Prim's (grow a tree greedily from one node, always adding the cheapest edge connecting the tree to a new node).

How Minimum Spanning Tree Works — Step by Step

Kruskal's Algorithm: 1. Sort all edges by weight in ascending order. 2. Initialize a Union-Find data structure where each node is its own component. 3. For each edge (u, v, w) in sorted order: a. If u and v are in different components (find(u) != find(v)), add this edge to the MST. b. Union the two components (union(u, v)). c. Stop when the MST has V-1 edges.

Prim's Algorithm (min-heap version): 1. Start from any node. Mark it visited. Push all its edges into a min-heap keyed by weight. 2. While the heap is non-empty and the MST has fewer than V-1 edges: a. Pop the minimum-weight edge (w, u, v). b. If v is already in the MST, skip (this edge would form a cycle). c. Add v to the MST. Add edge (u,v,w) to results. Push all edges from v to unvisited nodes.

Both algorithms produce the same MST (or an equally-weighted one). Time: O(E log E) for Kruskal's, O(E log V) for Prim's with a heap.

Worked Example — Tracing the Algorithm

Graph with 5 nodes (A-E) and edges: A-B:2, A-C:3, B-C:1, B-D:4, C-E:5, D-E:1

Kruskal's trace (edges sorted by weight): Sorted edges: B-C:1, D-E:1, A-B:2, A-C:3, B-D:4, C-E:5

Step 1: B-C:1 — B and C are in different components. Add to MST. Union(B,C). MST={B-C} Step 2: D-E:1 — D and E are in different components. Add to MST. Union(D,E). MST={B-C, D-E} Step 3: A-B:2 — A and B are in different components. Add to MST. Union(A,B,C). MST={B-C, D-E, A-B} Step 4: A-C:3 — A and C are in the SAME component. SKIP (would form cycle A-B-C). Step 5: B-D:4 — B is in {A,B,C}, D is in {D,E}. Add to MST. Union all. MST={B-C, D-E, A-B, B-D} MST has 4 edges = V-1 = 5-1. Done.

Total MST weight: 1+1+2+4 = 8 The edge C-E:5 was not needed — the path C-B-D-E achieves connectivity for less total cost.

Implementation

kruskal sorts all edges by weight then processes them with Union-Find. find uses iterative path halving for efficiency. union attaches by rank. An edge is added to the MST only when it connects two different components. The loop stops early once the MST has n-1 edges, avoiding unnecessary edge processing.

def kruskal(n, edges):
    """n = number of nodes (0..n-1), edges = list of (weight, u, v)"""
    edges.sort()
    parent = list(range(n))
    rank   = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return False
        if rank[ra] < rank[rb]: ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1
        return True

    mst = []
    for w, u, v in edges:
        if union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

# Node mapping: A=0,B=1,C=2,D=3,E=4
edges = [(2,0,1),(3,0,2),(1,1,2),(4,1,3),(5,2,4),(1,3,4)]
mst = kruskal(5, edges)
names = 'ABCDE'
total = sum(w for _,_,w in mst)
for u,v,w in mst:
    print(f'{names[u]}-{names[v]}: {w}')
print(f'Total MST weight: {total}')

Frequently Asked Questions