Minimum spanning trees

The problem: connect everything cheaply

A district wants to link all its villages by road. Many roads are possible, each with a building cost. Which roads should it build so that every village can reach every other, at the lowest total cost? The same question appears when laying fibre-optic cable between offices, electricity lines between towns, or water pipes in a housing society.

In graph words: the graph is undirected and weighted. A spanning tree is a set of edges that connects all V vertices with no cycle; it always has exactly V − 1 edges. A minimum spanning tree (MST) is a spanning tree with the smallest total weight. If the graph is disconnected, no spanning tree exists. There may be several MSTs with the same total when weights repeat.

Kruskal's algorithm

1. Sort all edges by weight, cheapest first.
2. Go through them in order. If an edge joins two vertices that are in DIFFERENT union-find groups, take it and union the groups.
3. If both ends are already in the same group, skip the edge: it would close a cycle.
4. Stop after taking V − 1 edges. If you run out of edges first, the graph is disconnected.

Why is the greedy choice safe? Split the vertices into any two sides. The cheapest edge that crosses between the sides always belongs to some MST (this is called the cut property). Each edge Kruskal takes is the cheapest edge joining its group to the rest, so it is always safe.

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

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

    chosen = []
    for w, u, v in sorted((w, u, v) for u, v, w in edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            chosen.append((u, v, w))
    return chosen

edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8)]
print(kruskal(4, edges))   # Output: [(0, 2, 1), (1, 2, 2), (1, 3, 5)]

Sorting costs O(E log E), and the union-find work is almost O(1) per edge, so Kruskal is O(E log E) time and O(V + E) space. Note that E log E and E log V are the same order, since E is at most V².

Prim's algorithm

Prim grows ONE tree. Start with any vertex. Keep a min-heap of edges that leave the tree. Pop the cheapest; if it leads to a vertex already in the tree, skip it; otherwise add that vertex, add the edge's weight to the total, and push all its edges. It looks like Dijkstra, but the heap key is the weight of the single edge, not the total distance from the start.

import heapq

def prim(n, adj, start=0):
    in_tree = [False] * n
    heap = [(0, start)]
    total = 0
    added = 0
    while heap and added < n:
        w, u = heapq.heappop(heap)
        if in_tree[u]:
            continue
        in_tree[u] = True
        total += w
        added += 1
        for v, wv in adj[u]:
            if not in_tree[v]:
                heapq.heappush(heap, (wv, v))
    return total if added == n else -1

adj = [[(1, 4), (2, 1)], [(0, 4), (2, 2), (3, 5)], [(0, 1), (1, 2), (3, 8)], [(1, 5), (2, 8)]]
print(prim(4, adj))   # Output: 8

Which one to use

The "connect all points" problem is the last case: every pair of points can be joined, at a cost equal to their Manhattan distance |x1 − x2| + |y1 − y2|. Keep, for every vertex not yet in the tree, the cheapest edge to the tree, and each round pick the smallest. That is O(V²) time and O(V) space, with no heap and no edge list.

Common mistakes

• Not checking that the result has V − 1 edges, so a disconnected graph gets a wrong "answer". Fix: count the edges taken (or vertices added).
• Using an MST to answer "shortest route from A to B". Fix: that is Dijkstra.
• In Prim, marking a vertex as in the tree when it is pushed instead of when it is popped. Fix: mark it when popped, like Dijkstra.
• Sorting edges by the wrong field, for example (u, v, w) tuples sorted by u. Fix: sort by weight, with key=lambda e: e[2] or by putting w first.
• Applying it to a directed graph. Fix: the MST is defined for undirected graphs; directed versions need different algorithms.