Minimum Spanning Tree — Prim & Kruskal

The problem

You need to connect a set of towns with roads (or computers with cables, or houses with water pipes). Each possible link has a cost. What is the cheapest way to connect everything?

You don’t need every link — just enough so that every node is reachable. The cheapest such set of edges is a Minimum Spanning Tree (MST):

• Spanning — it touches every vertex.
• Tree — connected and with no cycles, so exactly V − 1 edges.
• Minimum — the smallest possible total weight.

An MST is not the same as shortest paths (Dijkstra). Dijkstra minimises the distance from one source to each node; an MST minimises the total cost of the whole network.

Kruskal’s algorithm — cheapest edge first

1. Sort all edges by weight.
2. Go through them from cheapest to most expensive.
3. Accept an edge if its two endpoints are in different trees; reject it if they’re already connected (it would create a cycle).
4. Stop after V − 1 edges.

The cycle check uses a Disjoint Set (Union–Find): find(u) ≠ find(v) means “different trees”, and union(u, v) merges them. In the 3D model, nodes in the same tree share a colour, and rejected edge cards turn red.

Prim’s algorithm — grow one tree

1. Start the tree with any vertex.
2. Look at every edge that leaves the tree (one end inside, one outside).
3. Add the cheapest one, along with its new vertex.
4. Repeat until all vertices are in the tree.

With a min-heap (priority queue) for the candidate edges this runs in O(E log V). It’s very similar to Dijkstra — the only difference is the key: Prim uses the edge weight, Dijkstra the total distance from the source.

Why does greedy work here?

The cut property: for any way of splitting the vertices into two groups, the cheapest edge crossing between the groups belongs to some MST. Both algorithms only ever add such “cheapest crossing” edges, so they never make a mistake.

Code

def kruskal(n, edges):
    """edges: list of (weight, u, v) with vertices 0..n-1"""
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                        # different trees → no cycle
            parent[ru] = rv
            mst.append((u, v, w))
            total += w
    return total, mst

import heapq
def prim(adj, start=0):
    """adj[u] = list of (v, w)"""
    seen, total = {start}, 0
    heap = [(w, start, v) for v, w in adj[start]]
    heapq.heapify(heap)
    while heap and len(seen) < len(adj):
        w, u, v = heapq.heappop(heap)
        if v in seen:
            continue
        seen.add(v)
        total += w
        for x, wx in adj[v]:
            if x not in seen:
                heapq.heappush(heap, (wx, v, x))
    return total

# A B C D E F G = 0..6 (the sample graph from the 3D model)
edges = [(4,0,1),(2,0,2),(1,2,1),(5,1,3),(8,2,3),(10,2,4),(2,3,4),(6,3,5),(3,4,5),(5,4,6),(1,5,6)]
print(kruskal(7, edges)[0])   # 14

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

vector<int> parent;
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

int main() {
    int n = 7;
    vector<array<int,3>> edges = {{4,0,1},{2,0,2},{1,2,1},{5,1,3},{8,2,3},{10,2,4},
                                  {2,3,4},{6,3,5},{3,4,5},{5,4,6},{1,5,6}};
    sort(edges.begin(), edges.end());
    parent.resize(n);
    iota(parent.begin(), parent.end(), 0);
    int total = 0;
    for (auto [w, u, v] : edges)
        if (find(u) != find(v)) { parent[find(u)] = find(v); total += w; }
    cout << total << "\n";   // 14
}

Prim vs Kruskal

Where are MSTs used?

Designing networks (electric grids, roads, pipelines, LAN cabling), clustering (remove the most expensive MST edges to split data into groups), image segmentation, and as a building block in approximation algorithms such as the travelling-salesman 2-approximation.

Common mistakes

• Confusing MST with shortest path trees.
• In Kruskal, forgetting the cycle check (or checking with parent[u] == parent[v] instead of find).
• Running on a disconnected graph — you get a minimum spanning forest, not a tree.