Kruskal vs Prim: Minimum Spanning Tree Algorithms Compared

Kruskal's and Prim's algorithms solve the same problem, both are greedy, and both always produce a minimum spanning tree. They are still worth learning as a pair, because they look at the graph from opposite ends: Kruskal considers edges globally, cheapest first; Prim grows a single tree outwards from one vertex. Which one fits depends on how the graph is stored and how dense it is.

The problem it solves

You have a connected, undirected graph with a weight on every edge. Pick a subset of edges that connects every vertex, contains no cycle, and has the smallest possible total weight. That subset is a minimum spanning tree (MST). With V vertices it always has exactly V - 1 edges.

The picture to keep in mind is laying cable. Every pair of buildings you could connect has a price. You need every building reachable from every other, and you want to spend as little as possible. Redundant cables — ones that close a loop — are wasted money.

The intuition

Both algorithms rest on one fact, the cut property. Split the vertices into any two groups. Among the edges that cross between the groups, the cheapest one belongs to some minimum spanning tree. The reason: any spanning tree must cross that split somewhere, and if it used a more expensive crossing edge, swapping in the cheaper one would keep it a tree and lower the total.

The two algorithms apply that fact in different ways.

Kruskal sorts all edges by weight and walks the list. For each edge it asks: are the two endpoints already connected by edges I have kept? If not, keep it — it is the cheapest edge crossing between the two separate islands it joins. If they are already connected, the edge would close a cycle, so skip it. A union-find structure answers "already connected?" in nearly constant time.

Prim starts from any vertex and treats the tree-so-far as one island. At every step it takes the cheapest edge leaving the island — again the cut property — and pulls the vertex on the far side in. A min-heap of candidate edges makes "cheapest edge leaving" fast.

So Kruskal grows a forest that gradually merges; Prim grows one tree that gradually expands.

Watch it run

Four sites, five possible cables, sorted by price. Kruskal takes a–b for 1 and c–d for 2 — two separate islands. a–c for 3 joins them. Then b–c and b–d both arrive with their endpoints already on the same island, so each would only close a cycle and is skipped. Three edges for four vertices, total 6. Watch the island label under each vertex change as components merge.

The code

Both algorithms on the animation's graph. Kruskal uses union-find with path halving; Prim uses a heap and skips entries that went stale:

import heapq

def kruskal(n, edges):                          # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]       # path halving
            x = parent[x]
        return x
    total, kept = 0, []
    for w, u, v in sorted(edges):               # cheapest first, over the whole graph
        ru, rv = find(u), find(v)
        if ru != rv:                            # joins two islands: keep it
            parent[ru] = rv
            total += w
            kept.append((u, v))
    return total if len(kept) == n - 1 else None, kept

def prim(n, edges):
    adj = [[] for _ in range(n)]
    for w, u, v in edges:
        adj[u].append((w, v))
        adj[v].append((w, u))
    seen, total, frontier = [False] * n, 0, [(0, 0)]    # grow from vertex 0
    while frontier:
        w, u = heapq.heappop(frontier)          # cheapest edge leaving the tree
        if seen[u]:
            continue                            # stale: u joined by a cheaper edge
        seen[u] = True
        total += w
        for edge in adj[u]:
            if not seen[edge[1]]:
                heapq.heappush(frontier, edge)
    return total if all(seen) else None

a, b, c, d = range(4)
edges = [(1, a, b), (2, c, d), (3, a, c), (4, b, c), (5, b, d)]
print(kruskal(4, edges))                        # (6, [(0, 1), (2, 3), (0, 2)])
print(prim(4, edges))                           # 6

Both return None for a disconnected graph, where no spanning tree exists — Kruskal because it keeps fewer than V - 1 edges, Prim because some vertex is never reached.

Greedy algorithms deserve suspicion, so both are checked against exhaustive search. On small random graphs, try every set of V - 1 edges, keep those that connect everything without a cycle, and take the cheapest. Weights are drawn from 1 to 9 so ties are common, since ties are where a greedy choice is most likely to go wrong:

import random
from itertools import combinations

def mst_brute(n, edges):                        # every set of n - 1 edges; keep trees
    best = None
    for pick in combinations(edges, n - 1):
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                x = parent[x]
            return x
        joined = 0
        for w, u, v in pick:
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv
                joined += 1
        if joined == n - 1:                     # n - 1 edges and no cycle: a tree
            weight = sum(w for w, _, _ in pick)
            best = weight if best is None else min(best, weight)
    return best

random.seed(7)
ok = True
for _ in range(1500):
    n = random.randint(1, 6)
    pairs = [(u, v) for u in range(n) for v in range(u + 1, n) if random.random() < 0.6]
    edges = [(random.randint(1, 9), u, v) for u, v in pairs]    # repeated weights on purpose
    want = mst_brute(n, edges)
    ok &= kruskal(n, edges)[0] == want == prim(n, edges)
print(ok)                                       # True

With repeated weights the tree itself may not be unique, so the check compares total weight, which is.

The complexity

• Kruskal: sorting dominates, O(E log E). The union-find operations add almost nothing. Memory O(V) beyond the edge list.
• Prim with a binary heap: each edge can push one heap entry, so O(E log E), usually written O(E log V) since log E is at most 2 log V. Memory O(E) for the heap in the lazy version above.
• Prim with an adjacency matrix and no heap: scan all vertices for the cheapest each round, O(V²). On a dense graph where E is close to V², this beats the heap versions.

Rule of thumb: an edge list, or a sparse graph, suits Kruskal. An adjacency list or matrix of a dense graph suits Prim.

Where it goes wrong

• Applying it to a directed graph. Neither algorithm finds a minimum spanning arborescence; that is a different problem with a different algorithm.
• Assuming shortest paths come for free. The MST minimises the total, not the distance between any particular pair. The tree path between two vertices can be much longer than their shortest path.
• Stale heap entries in Prim. A vertex can sit in the heap several times with different weights. Without the seen check it is added twice and the total is wrong.
• Cycle detection by DFS in Kruskal. Correct, but it turns each check into O(V). Union-find is the reason Kruskal is fast.

The union-find structure Kruskal depends on is covered in path compression, and Prim has its own lesson: Prim's spanning tree.

How to say it in an interview

"Both rely on the cut property: the cheapest edge crossing any split of the vertices is safe to add. Kruskal sorts all edges and keeps each one whose endpoints are in different union-find sets — O(E log E). Prim grows one tree from a start vertex and repeatedly takes the cheapest edge leaving it from a min-heap — O(E log V). I'd use Kruskal for an edge list or a sparse graph, and Prim for a dense graph in an adjacency structure."

Stating the cut property in one sentence, rather than just naming the algorithms, is what shows you know why a greedy choice is safe here when it so often is not.