How do Kruskal and Prim build a minimum spanning tree?

Question

Accepted Answer

A **minimum spanning tree (MST)** connects all vertices of a weighted, connected graph with the **minimum total edge weight** and no cycles. **Kruskal** and **Prim** are the two classic greedy algorithms.

## Kruskal (sort edges, union-find)

Sort all edges by weight; add the cheapest edge that does not form a cycle.

```python
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 compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim (grow a tree with a min-heap)

Start from any vertex; repeatedly add the cheapest edge leaving the current tree.

## Comparison

| | Kruskal | Prim |
|---|--------|------|
| Approach | sort edges + union-find | grow from a node + heap |
| Time | O(E log E) | O(E log V) |
| Best for | sparse graphs | dense graphs |

## When to use / pitfalls

Use MST for **network design** — laying cable, water pipes, clustering. Both are greedy and provably optimal here. Kruskal needs union-find to avoid cycles efficiently.

## Why it matters

MST minimizes the cost of connecting everything — directly applicable to infrastructure and network layout.

It is a clean case where greedy is provably optimal, reinforcing greedy-choice reasoning.

Kruskal also showcases union-find, a structure with wide algorithmic reach.

	Kruskal	Prim
Approach	sort edges + union-find	grow from a node + heap
Time	O(E log E)	O(E log V)
Best for	sparse graphs	dense graphs