Minimum Spanning Tree (Kruskal & Prim)

A Minimum Spanning Tree (MST) connects every vertex in a weighted, undirected graph using the minimum possible total edge weight, with no cycles. Think of laying network cable between offices: you need every office connected to the network somehow, you want to minimize total cable cost, and there's never a reason to connect two offices that are already connected through some other path — that would just be wasted cable forming a cycle. This lesson covers the two classic ways to build one: Kruskal's algorithm and Prim's algorithm.

The Example Graph

Both algorithms below run on this same 5-vertex weighted graph:

        A
      /   \
    2       6
    /         \
   B --- 3 --- C
   |  \        |
   8    5      7
   |      \    |
   D ------4---E

Edges: A-B(2), A-C(6), B-C(3), B-D(8), B-E(5), C-E(7), D-E(4)
Total vertices: 5 (A,B,C,D,E) -- an MST will use exactly 5-1 = 4 edges.

Kruskal's Algorithm

Kruskal's is greedy at the level of individual edges: sort all edges by weight, then walk them from cheapest to most expensive, adding each edge to the MST unless it would create a cycle (i.e., unless both endpoints are already connected to each other through edges already chosen).

"Already connected" is checked with a Union-Find (Disjoint Set) structure: each vertex starts in its own group; find() tells you which group a vertex belongs to, and union() merges two groups. Two vertices in the same group already have a path between them, so adding an edge between them would only create a cycle.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # every vertex starts as its own group

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression: flatten as we go
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # already connected -- adding this edge would create a cycle
        self.parent[root_x] = root_y  # merge the two groups
        return True

def kruskal_mst(n, edges):
    # edges: list of (weight, u, v) tuples
    edges = sorted(edges)  # cheapest edges first
    uf = UnionFind(n)
    total_weight = 0
    edges_used = 0

    for weight, u, v in edges:
        if uf.union(u, v):        # True means no cycle -- safe to add
            total_weight += weight
            edges_used += 1
            if edges_used == n - 1:
                break  # MST complete: n vertices need exactly n-1 edges

    return total_weight

On the example graph (A=0, B=1, C=2, D=3, E=4): sorted edges are A-B(2), B-C(3), D-E(4), B-E(5), A-C(6), C-E(7), B-D(8). Add A-B(2) — no cycle. Add B-C(3) — no cycle. Add D-E(4) — no cycle. Add B-E(5) — no cycle, and now 4 edges are used (n-1 = 4), so we stop. Skip everything after. MST edges: {A-B, B-C, D-E, B-E}, total weight = 2+3+4+5 = 14.

Time complexity: O(E log E) — dominated by sorting the edges; the Union-Find operations with path compression are nearly O(1) amortized. Space complexity: O(V + E) — the Union-Find parent list (O(V)) plus storing the edge list (O(E)).

Prim's Algorithm

Prim's is greedy at the level of vertices: start from any single vertex, and repeatedly grow the tree by adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. This is structurally the same shape as Dijkstra's algorithm — a heapq min-heap of candidate edges, always expanding via the cheapest option — except Prim's compares edge weights to grow a tree, while Dijkstra compares cumulative path distances to find shortest paths.

import heapq

def prim_mst(n, adj, start):
    # adj: dict mapping vertex -> list of (neighbor, weight)
    in_mst = set()
    min_heap = [(0, start)]  # (weight, vertex), ordered by weight
    total_weight = 0

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)
        if vertex in in_mst:
            continue  # already in the tree via a cheaper edge -- skip

        in_mst.add(vertex)
        total_weight += weight

        for neighbor, edge_weight in adj[vertex]:
            if neighbor not in in_mst:
                heapq.heappush(min_heap, (edge_weight, neighbor))  # candidate edge to grow the tree

    return total_weight

Starting from A on the same graph: pop A (weight 0), mark in MST, push A-B(2) and A-C(6). Pop B(2), mark in MST, total_weight=2, push B-C(3), B-D(8), B-E(5). Pop B-C(3) (cheapest available), mark C in MST, total_weight=5, push C-E(7) (A-C(6) still sits in the heap but leads to an already-visited vertex once popped). Pop B-E(5), mark E in MST, total_weight=10, push D-E(4) — this replaces the need for B-D(8). Pop D-E(4), mark D in MST, total_weight=14. Same MST edges and same total weight as Kruskal's found, just discovered in a different order — this is expected, since for a graph with distinct edge weights the MST is unique.

Time complexity: O(E log V) using a binary heap — every edge may be pushed onto the heap once (O(log V) per push/pop), similar to Dijkstra's complexity with a heap. Space complexity: O(V + E) — the adjacency list (O(V + E)) plus the heap, which holds at most O(E) candidate edges.

Kruskal vs Prim: When to Use Which