Minimum spanning tree explained: Kruskal's and Prim's algorithms

What problem a minimum spanning tree solves

Suppose you must connect several buildings with cable, several towns with roads, or several servers with network links, and each possible connection has a cost. You want every place to be connected (directly or indirectly) at the lowest total cost. Extra connections that form a loop are never needed, so the answer is a tree: V nodes joined by exactly V − 1 edges. That tree is the minimum spanning tree.

An MST is not a shortest-path tree. It minimizes the total weight of all edges, not the distance from one start node to the others.

Why the greedy choice works: the cut property

Split the nodes into any two groups. Among the edges that cross between the groups, the lightest one belongs to some minimum spanning tree. Both algorithms rely on this fact:

If all edge weights are different, the MST is unique, so both algorithms return the same tree. With equal weights there can be several MSTs with the same total.

Worked example, step by step

Undirected graph with 5 nodes and edges A–B 4, A–C 3, B–C 1, B–D 2, C–D 4, D–E 2, C–E 5.

Kruskal's algorithm, edges sorted by weight:

Prim's algorithm from A: the cheapest edge leaving {A} is A–C (3); from {A, C} it is C–B (1); from {A, B, C} it is B–D (2); from {A, B, C, D} it is D–E (2). Same tree, total weight 3 + 1 + 2 + 2 = 8.

Kruskal's algorithm in Python

Union-find keeps a parent pointer per node. find returns the representative of a node's component, and two nodes are connected exactly when they have the same representative.

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

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

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

A full union-find also uses union by rank or size, which keeps the trees shallow. Path halving alone is already fast in practice. You can stop the loop early once the tree has V − 1 edges.

Prim's algorithm in Python

Prim's algorithm needs an adjacency list. It uses lazy deletion like Dijkstra's algorithm: push every edge that leaves the tree, and skip edges whose far end is already in the tree.

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

Time and space complexity

Because E is at most V², log E is at most 2 log V, so O(E log E) and O(E log V) are the same order.

Variants and common mistakes

• Disconnected graph: there is no spanning tree. Kruskal then returns a minimum spanning forest (one tree per component); Prim from one start covers only that start's component. Check that the tree has V − 1 edges.
• Maximum spanning tree: sort edges in descending order (or negate the weights). Negative weights are fine for both algorithms.
• Directed graphs need a different algorithm (minimum arborescence, Chu-Liu/Edmonds); Kruskal and Prim do not apply.
• Clustering: run Kruskal and stop when k components remain. The result is a single-linkage clustering into k groups.
• Borůvka's algorithm, from 1926, adds the cheapest edge from every component at once and parallelizes well.

When to use it and real-world uses

• Network design: the cheapest way to connect sites with cable, pipes or roads, when any connected layout is acceptable.
• Approximation algorithms: an MST gives a tour at most twice the optimal length for the metric traveling salesman problem.
• Clustering and image segmentation by cutting the heaviest MST edges.
• Interview problems: min cost to connect all points, connecting cities with minimum cost, optimize water distribution in a village.