Minimum Spanning Trees

You're wiring up redundant network links between a set of colocated servers so every pair can reach every other pair, and each possible link has a different cost. You don't need every link — you need the cheapest set of links that still connects everything. That's a minimum spanning tree (MST): a subset of edges that connects all $V$ nodes, contains no cycle, and has the smallest possible total weight. A tree on $V$ nodes always has exactly $V-1$ edges, which is also why an MST always has exactly $V-1$ edges — any fewer and something is disconnected, any more and there's a cycle you could cut for free.

Two greedy algorithms, same answer

Kruskal's algorithm: sort all edges by weight, ascending. Walk the sorted list and add an edge only if it connects two components that aren't already connected — that is, only if it doesn't create a cycle. A union-find (disjoint-set) structure answers "are these two nodes already connected" in near-$O(1)$, so the whole algorithm is dominated by the sort: $O(E \log E)$.

Prim's algorithm: start from any single node and grow one connected tree, at each step adding the cheapest edge that connects the current tree to a node not yet in it — the same priority-queue machinery as Dijkstra, just minimising "edge into the tree" instead of "distance from the source." Cost is $O(E \log V)$ with a binary heap.

Both are greedy and both are provably correct, which is unusual — most greedy strategies need a cycle-avoidance or exchange argument, and MST has one: the cut property says that for any way of splitting the nodes into two groups, the cheapest edge crossing that split must be in some MST. Kruskal exploits this globally by weight order; Prim exploits it locally around the growing tree.

Worked example: Kruskal by hand

Edges sorted ascending: A-B 2, B-C 3, B-D 4, C-E 5, A-D 7, D-E 9. Add A-B (connects A, B). Add B-C (connects C in). Add B-D (connects D in). Add C-E (connects E in) — 4 edges, all 5 nodes connected, done. A-D is skipped: A and D are already connected through B, so adding it would only create a cycle. Total weight: $2+3+4+5=14$.

def kruskal(n, edges):                     # edges: (w, u, v); O(E log E)
    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):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            mst.append((u, v, w))
            total += w
    return mst, total

Where it shows up

Interview framing: "connecting cities with minimum cost" and "min cost to supply water" (LeetCode 1168) are MST in disguise. On a desk, clustering correlated assets into a minimum-cost tree (used in portfolio hierarchical clustering and the classic Mantegna "minimum spanning tree of stocks" studies) applies MST directly to a correlation-distance graph, and network topology design for low-latency infrastructure between colocated servers is the same problem with real cable costs.