Minimum Spanning Tree: Kruskal and Prim
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A company must connect its offices with cables. Each possible cable has a price. The goal is to link every office at the smallest total price, with no wasted cable. That set of cables is a minimum spanning tree.
Connect everything, spend the least
A minimum spanning tree (MST) of a connected, weighted, undirected graph is a set of V - 1 edges that connects all nodes with the smallest possible total weight and no cycle.
A tree that touches all V nodes needs exactly V - 1 edges. Fewer edges leave a node alone, and more edges make a loop that can be cut. Among all such trees, pick the one with the smallest total weight.
Example 1 · Brute force: try every set of V - 1 edges
from itertools import combinations
edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 6)]n = 5
def is_tree(chosen): parent = list(range(n))
def find(x): while parent[x] != x: x = parent[x] return x
for u, v, w in chosen: ru, rv = find(u), find(v) if ru == rv: return False parent[ru] = rv return True
best = min(sum(w for _, _, w in c) for c in combinations(edges, n - 1) if is_tree(c))print(best)12
What this code does
- It tries all choices of 4 edges out of 6, which is 15 sets. In general that is C(E, V - 1), far too many.
- A set of V - 1 edges with no cycle must connect all V nodes.
Kruskal: take the cheapest edge that makes no loop
Sort the edges by weight. Go through them from the cheapest. Keep an edge if its two ends are in different groups, and merge the groups. Union-Find answers that question almost instantly.
parent = list(range(n))total = 0for u, v, w in sorted(edges, key=lambda e: e[2]): ru, rv = find(parent, u), find(parent, v) if ru != rv: parent[ru] = rv total += wExample 2 · Kruskal's algorithm
def find(parent, x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
def kruskal(n, edges): parent = list(range(n)) total, chosen = 0, [] for u, v, w in sorted(edges, key=lambda e: e[2]): ru, rv = find(parent, u), find(parent, v) if ru != rv: parent[ru] = rv total += w chosen.append((u, v, w)) return total, chosen
edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 6)]n = 5
print(kruskal(n, edges)[0])12
What this code does
- Sorted by weight, the edges are 1, 2, 3, 4, 4, 6. The edge (2, 3, 4) is skipped because 2 and 3 are already linked through node 1.
- Total weight is 1 + 2 + 3 + 6 = 12.
Sorting costs O(E log E), and the Union-Find work is almost O(E). So the time is O(E log E) and the space is O(V + E).
Prim: grow one tree outward
Start from any node. Keep a heap of edges that leave the tree, as pairs (weight, node). Pop the cheapest. If its node is new, add it to the tree and push the edges that leave it.
seen = [False] * nheap = [(0, 0)]total = 0while heap: w, u = heapq.heappop(heap) if seen[u]: continue seen[u] = True total += w for v, wt in graph[u]: if not seen[v]: heapq.heappush(heap, (wt, v))Example 3 · Prim's algorithm
import heapq
edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 6)]n = 5
graph = [[] for _ in range(n)]for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w))
seen = [False] * nheap = [(0, 0)]total = 0while heap: w, u = heapq.heappop(heap) if seen[u]: continue seen[u] = True total += w for v, wt in graph[u]: if not seen[v]: heapq.heappush(heap, (wt, v))print(total)12
What this code does
- Both algorithms reach the same total. The set of chosen edges may differ only when weights tie.
- Prim starts at node 0 and always adds the cheapest edge that leaves the tree.
Example 4 · List the chosen edges
def find(parent, x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
def kruskal(n, edges): parent = list(range(n)) total, chosen = 0, [] for u, v, w in sorted(edges, key=lambda e: e[2]): ru, rv = find(parent, u), find(parent, v) if ru != rv: parent[ru] = rv total += w chosen.append((u, v, w)) return total, chosen
edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 6)]n = 5
total, chosen = kruskal(n, edges)print(total)for u, v, w in chosen: print(u, v, w)12 1 2 1 1 3 2 0 2 3 3 4 6
What this code does
sorted(..., key=lambda e: e[2])sorts the edge tuples by their third item, the weight.- The result has exactly n - 1 = 4 edges.
Each edge is pushed at most twice, so the time is O(E log V) and the space is O(V + E). It reads like Dijkstra, but the key is the edge weight alone, not the distance from the start.
Choosing one, and a graph that is not connected
Kruskal works straight from an edge list and is short. Prim works best from an adjacency list on dense graphs. If a connected graph has V nodes, an MST has V - 1 edges. Fewer chosen edges mean the graph is split in parts.
Example 5 · A graph that cannot be connected
def find(parent, x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
def kruskal(n, edges): parent = list(range(n)) total, chosen = 0, [] for u, v, w in sorted(edges, key=lambda e: e[2]): ru, rv = find(parent, u), find(parent, v) if ru != rv: parent[ru] = rv total += w chosen.append((u, v, w)) return total, chosen
edges = [(0, 1, 2), (1, 2, 3), (3, 4, 1)]n = 5total, chosen = kruskal(n, edges)if len(chosen) == n - 1: print(total)else: print('not connected', len(chosen))not connected 3
What this code does
- Nodes 0, 1, 2 and nodes 3, 4 are two separate parts, so only 3 edges can be chosen where 4 are needed.
- Always compare the number of chosen edges with n - 1 before you trust the total.
Example 6 · Maximum spanning tree
def find(parent, x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x
def kruskal(n, edges): parent = list(range(n)) total, chosen = 0, [] for u, v, w in sorted(edges, key=lambda e: e[2], reverse=True): ru, rv = find(parent, u), find(parent, v) if ru != rv: parent[ru] = rv total += w chosen.append((u, v, w)) return total, chosen
edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 6)]n = 5
print(kruskal(n, edges)[0])17
What this code does
- Sorting from the heaviest edge gives the maximum spanning tree. Nothing else changes.
- The total is 6 + 4 + 4 + 3 = 17.
Next step
Check your understanding
11 quick questions