Minimum Spanning Tree

Minimum Spanning Tree | Algoryva

First, the naive way

Try every set of V − 1 edges

An MST uses exactly V − 1 edges, so one approach is to try every choice of V − 1 edges out of E, keep those that connect everything, and take the cheapest.

It is correct, but the number of choices is the binomial C(E, V − 1). With 20 nodes and 40 edges that is already about 1.3 × 10¹¹ subsets (131 billion), and real graphs are far bigger.

python

from itertools import combinations

def connected(n, chosen):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for a, b, w in chosen:
        parent[find(a)] = find(b)
    return len({find(i) for i in range(n)}) == 1

def mst_bruteforce(n, edges):
    best = None
    for chosen in combinations(edges, n - 1):          # try every set of n - 1 edges
        if connected(n, chosen):
            cost = sum(w for a, b, w in chosen)
            if best is None or cost < best:
                best = cost
    return best

print(mst_bruteforce(4, [(0, 1, 1), (1, 2, 4), (2, 3, 2), (0, 2, 3), (0, 3, 10)]))   # 6
print(mst_bruteforce(3, [(0, 1, 5)]))   # None

Cost: O(C(E, V − 1) × V): astronomically large; fine only for toy graphs.

Worked by hand

Kruskal by hand

The same graph, edges sorted by weight (ties broken alphabetically).

edge	weight	groups before	decision
C–F	2	C and F are separate	take: {C,F}
D–E	6	separate	take: {D,E}
A–B	7	separate	take: {A,B}
A–C	9	{A,B} and {C,F}	take: {A,B,C,F}
E–F	9	{D,E} and {A,B,C,F}	take: all six connected
…	10 to 15	already one group	skip every remaining edge

1
Five edges for six nodes
V − 1 = 5 edges were taken, with total weight 2 + 6 + 7 + 9 + 9 = 33. We can stop as soon as the tree has V − 1 edges.
2
Ties
A–C and E–F both weigh 9. Taking them in the other order gives the same total. The set of edges may differ between runs, but the total weight cannot.

Implementation

Kruskal with Union-Find

Sort edges by weight, then use Union-Find to test whether an edge's endpoints are already connected.

Plan in plain steps

pseudocode

sort edges by weight
for each edge (a, b, w) in that order:
    if find(a) != find(b):    # different groups
        union them; add w to the total; keep the edge

python

def kruskal(n, edges):
    parent = list(range(n))

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

    total, used = 0, []
    for w, a, b in sorted((w, a, b) for a, b, w in edges):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            total += w
            used.append((a, b, w))
    return total, used

edges = [(0, 1, 7), (0, 2, 9), (0, 5, 14), (1, 2, 10), (1, 3, 15), (2, 3, 11), (2, 5, 2), (3, 4, 6), (4, 5, 9)]
total, used = kruskal(6, edges)
print(total)   # 33
print(used)   # [(2, 5, 2), (3, 4, 6), (0, 1, 7), (0, 2, 9), (4, 5, 9)]
print(len(used) == 6 - 1)   # True
total2, used2 = kruskal(4, [(0, 1, 1), (2, 3, 1)])
print(len(used2) == 4 - 1)   # False

Reading the code

›Sorting tuples (w, a, b) sorts by weight first, then by endpoints, giving a deterministic order.
›find uses path halving (parent[x] = parent[parent[x]]) so repeated finds stay fast; this is the Union-Find from its own lesson, written compactly.
›If the final used has fewer than V − 1 edges, the graph was disconnected (last line: 2 edges for 4 nodes).
›The cost is dominated by the sort, O(E log E), plus almost-constant Union-Find work per edge.

Implementation

Prim with a heap

Start from any node. Keep a heap of edges leaving the tree built so far, each keyed by weight. Pop the cheapest; if it leads to a new node, add that node and push its edges.

python

import heapq

def prim(n, edges, start=0):
    g = [[] for _ in range(n)]
    for a, b, w in edges:
        g[a].append((b, w))
        g[b].append((a, w))
    seen = [False] * n
    pq = [(0, start)]
    total, count = 0, 0
    while pq:
        w, u = heapq.heappop(pq)
        if seen[u]:
            continue
        seen[u] = True
        total += w
        count += 1
        for v, wt in g[u]:
            if not seen[v]:
                heapq.heappush(pq, (wt, v))
    return total if count == n else -1

edges = [(0, 1, 7), (0, 2, 9), (0, 5, 14), (1, 2, 10), (1, 3, 15), (2, 3, 11), (2, 5, 2), (3, 4, 6), (4, 5, 9)]
print(prim(6, edges))   # 33
print(prim(6, edges, start=4))   # 33
print(prim(4, [(0, 1, 1), (2, 3, 1)]))   # -1
print(prim(1, []))   # 0

Reading the code

›It is almost line for line Dijkstra, with one change: the heap key is the edge weight wt, not the total distance d + w.
›seen[u] makes stale heap entries harmless: a node popped a second time is ignored.
›count == n checks that every node was reached, returning -1 for a disconnected graph (the third call).
›Starting from a different node gives the same total (33), because the MST weight does not depend on the start.

Worked problem

Connect all the points cheaply

The problem

Given n points on a plane, the cost to connect two points is their Manhattan distance |x₁ − x₂| + |y₁ − y₂|. Find the minimum total cost to connect all the points so that every point is reachable from every other.

Every pair of points is a possible edge, so the graph is complete: about n² / 2 edges. Sorting all of them would work but wastes time.
Use Prim's algorithm with an array instead of a heap: keep for each point the cheapest known cost to attach it to the tree.
Each round attach the unused point with the smallest cost, then update the others' costs using the new point.

python

def min_cost_connect(points):
    n = len(points)
    INF = float("inf")
    best = [INF] * n
    best[0] = 0
    used = [False] * n
    total = 0
    for _ in range(n):
        u = -1
        for i in range(n):
            if not used[i] and (u == -1 or best[i] < best[u]):
                u = i
        used[u] = True
        total += best[u]
        for v in range(n):
            if not used[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                if d < best[v]:
                    best[v] = d
    return total

print(min_cost_connect([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]))   # 20
print(min_cost_connect([[3, 12], [-2, 5], [-4, 1]]))   # 18
print(min_cost_connect([[0, 0]]))   # 0

Takeaway. On a complete graph, Prim in O(n²) beats sorting all edges. The edges are never stored: distances are computed when needed (an *implicit graph*). The 20 in the first example is the known answer for those five points.

Worked problem

How many cables are redundant?

The problem

There are n computers and a list of cables (pairs). Some cables are redundant: removing them leaves exactly the same groups of connected computers. What is the largest number of cables you can remove?

A minimal wiring that keeps each group connected needs a spanning tree per group: n − components cables in total.
So the answer is len(cables) − (n − components).
Count components with Union-Find: start at n and subtract 1 whenever a cable merges two groups.

python

def extra_cables(n, cables):
    parent = list(range(n))

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

    components = n
    for a, b in cables:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            components -= 1
    return len(cables) - (n - components)

print(extra_cables(4, [(0, 1), (1, 2), (2, 0), (2, 3)]))   # 1
print(extra_cables(6, [(0, 1), (1, 2), (3, 4)]))   # 0
print(extra_cables(3, [(0, 0), (0, 1), (0, 1)]))   # 2

Takeaway. Counting what you *can* keep (a spanning forest) tells you what you can discard. Self-loops and repeated cables are always redundant, and the formula already counts them.

Wrap-up

Remember this

A minimum spanning tree connects all nodes with V − 1 edges and the smallest possible total weight.
The cut property says the lightest edge across any split of the nodes is safe, which justifies greedy choices.
Kruskal sorts edges and uses Union-Find to skip cycle-forming ones; Prim grows one tree with a heap, like Dijkstra with a different key.
A disconnected graph has no spanning tree: check that V − 1 edges were used.
MSTs answer “connect everything cheaply”, not “cheapest route between two nodes”.

Cheat sheet

Spanning tree: connects V nodes with V − 1 edges, no cycle
Kruskal: sort edges; take if find(a) != find(b); stop at V − 1 edges
Prim: grow from a node; heap of (edge weight, node); skip seen
Cut property: the lightest edge across any cut is in some MST
Cost: Kruskal O(E log E) · Prim O(E log V) or O(V²) dense
Redundant edges: E − (V − components)

Top traps to avoid

Confusing the MST with shortest paths.
Forgetting the cycle check in Kruskal.
Not checking for a disconnected graph.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.How many edges does a spanning tree of a connected graph with 10 nodes have?
2.In Kruskal's algorithm, when is an edge skipped?
3.In the lesson's graph the MST total weight is 33. How many edges does it contain?
4.What dominates the running time of Kruskal's algorithm?
5.“Connect n cities with roads at minimum total cost so every city can reach every other” is:
6.Is the path between two nodes inside the MST always their shortest path in the original graph?
7.Kruskal on the edges (1,2,1), (2,3,2), (1,3,3), (3,4,4), sorted by weight with union-find. What is the total weight of the minimum spanning tree?
8.Kruskal on the same four edges. How many edges does the minimum spanning tree use?
9.A triangle with edges (1,2,1), (2,3,1), (1,3,5). What is the total weight of its minimum spanning tree?
10.Why is Kruskal's choice always safe to add?
11.Kruskal's algorithm on m edges, sorting first: what is the running time?
12.Which structure does Kruskal use to detect cycles?
13.How many edges does a minimum spanning tree on 5 nodes have?
14.When can a graph have more than one minimum spanning tree?
15.Prim's algorithm grows the tree from one node. Which edge does it add each step?

Minimum Spanning Tree

After this lesson you will be able to

Builds on

Unlocks

Wiring a village

Spanning trees and the cut property

Try every set of V − 1 edges

Keep taking the cheapest edge that does not waste money

Kruskal's algorithm

Prim's algorithm: grow one tree from A

Kruskal by hand

Kruskal with Union-Find

Reading the code

Prim with a heap

Reading the code

Costs, and Kruskal versus Prim

Edge cases

Mistakes to avoid

How to spot an MST problem

Connect all the points cheaply

How many cables are redundant?

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up1 problem

Core1 problem