Minimum Spanning Trees: Connecting Networks Efficiently

A telecom company has just won a contract to bring fibre-optic internet to six towns in a district. Survey teams have already measured the cost of laying cable along every possible route between town pairs — some routes cross flat farmland and are cheap, others cross rivers or hills and are expensive. The company does not need to build a cable along every possible route; it only needs every town to be able to reach every other town, directly or by hopping through intermediate towns. The question the network planners must answer is blunt and expensive: which routes should we actually build, and which should we skip, so that every town is connected while total construction cost is as low as possible?

This is not a made-up scenario for a textbook — it is exactly the kind of decision that shows up whenever someone designs a physical network on a budget: laying electrical grid lines between substations, routing water pipelines between colonies, or wiring computers in a school lab with the least cable. All of these problems share one shape, and that shape has a name: the Minimum Spanning Tree, or MST. By the end of this chapter you will be able to solve the six-town problem above by hand, and you will know two different algorithms — Kruskal's and Prim's — that a computer uses to solve it for networks with millions of connections.

A quick refresher: graphs and weights

A graph is a collection of points, called vertices (the towns, in our story), joined by connections called edges (the possible cable routes). When each edge carries a number describing its cost, distance, or time, we call it a weighted graph. A graph is connected if you can travel from any vertex to any other vertex by following some sequence of edges — even if that means passing through other vertices along the way.

Our six towns — label them A, B, C, D, E, and F — and the routes the survey team costed out (in lakh rupees) are:

• A–B: ₹4 lakh
• A–C: ₹8 lakh
• B–C: ₹3 lakh
• B–D: ₹7 lakh
• C–D: ₹2 lakh
• C–E: ₹5 lakh
• D–E: ₹6 lakh
• D–F: ₹9 lakh
• E–F: ₹1 lakh

Nine possible routes connect six towns. If the company built every single one, total cost would be 4+8+3+7+2+5+6+9+1 = ₹45 lakh, and — importantly — it would be a wasteful design, because several of those routes are redundant: you could delete some of them and every town would still be reachable from every other town. The planning problem is to find the cheapest subset of routes that keeps everyone connected.

Why the answer must be a tree, not just "some edges"

Suppose the company builds A–B, B–C, and also A–C. Look closely: A, B, and C are already connected through A–B and B–C alone (A reaches C by going through B). The route A–C forms a cycle — a closed loop A→B→C→A — and any edge that closes a cycle is unnecessary for connectivity. You could remove A–C, keep every town reachable, and save ₹8 lakh. This is the central insight of the whole chapter: a minimum-cost connecting network never contains a cycle, because a cycle always contains at least one edge you could delete for free (in terms of connectivity) while saving money.

A connected graph with no cycles has a special name: a tree. And a tree that touches every single vertex of the original graph — leaving none of the six towns stranded — is called a spanning tree. There is a clean numerical fact worth memorising: a spanning tree on n vertices always has exactly n − 1 edges — never more (that would force a cycle) and never fewer (that would leave something disconnected). For our six towns, every valid spanning tree has exactly 5 edges, regardless of which 5 you pick, as long as they connect everyone without looping.

Among all the possible spanning trees you could draw on this graph — and there are many — the Minimum Spanning Tree is the one whose edge weights add up to the smallest possible total. That is the object the telecom company is actually hunting for.

The graph, and its MST, drawn out

Before working through an algorithm, look at the picture. The diagram below shows all nine possible routes. The five solid blue edges form the Minimum Spanning Tree; the four dashed grey edges are routes that exist but are correctly left unbuilt because including them would either create a cycle or simply cost more than necessary.

The five blue edges — A–B, B–C, C–D, C–E, E–F — connect all six towns and add up to 4 + 3 + 2 + 5 + 1 = ₹15 lakh. No other combination of five connecting edges costs less, as the algorithms below will prove step by step. Notice how much cheaper this is than building all nine routes (₹45 lakh) — the MST doesn't just avoid redundancy, it finds the cheapest possible skeleton.

Kruskal's Algorithm: sort every edge, then greedily accept the cheap ones

Kruskal's algorithm has a refreshingly simple idea behind it: look at all the edges in the whole graph, sorted from cheapest to most expensive, and walk down that list accepting an edge into your growing tree unless accepting it would create a cycle (which means both its endpoints are already connected to each other through edges you have already accepted).

Sorting our nine edges by weight gives: E–F(1), C–D(2), B–C(3), A–B(4), C–E(5), D–E(6), B–D(7), A–C(8), D–F(9). Now walk through them one at a time, keeping track of which towns are already joined into the same group:

1. E–F (₹1 lakh): E and F are in separate, unconnected groups. Accept it. Groups so far: {E,F}, {A}, {B}, {C}, {D}.
2. C–D (₹2 lakh): C and D are in separate groups. Accept it. Groups: {E,F}, {C,D}, {A}, {B}.
3. B–C (₹3 lakh): B is alone, C is in {C,D}. Different groups — accept it. Groups: {E,F}, {B,C,D}, {A}.
4. A–B (₹4 lakh): A is alone, B is in {B,C,D}. Different groups — accept it. Groups: {E,F}, {A,B,C,D}.
5. C–E (₹5 lakh): C is in {A,B,C,D}, E is in {E,F}. Different groups — accept it. Groups merge into one: {A,B,C,D,E,F}. All six towns are now in a single group, and we have accepted exactly 5 edges (= n − 1). The tree is complete — stop here.
6. D–E, B–D, A–C, D–F are never even examined, because the algorithm can stop the moment it has n − 1 edges. (For the record: each of them, if you checked, connects two towns already in the same group, so each would be rejected as a cycle-former.)

Total cost: 1 + 2 + 3 + 4 + 5 = ₹15 lakh — matching the picture above exactly.

The one piece of machinery Kruskal's algorithm needs is a fast way to answer "are these two towns already in the same group?" A simple and standard tool for this is called Union–Find (or Disjoint Set): each vertex points to a "parent," and following parent pointers upward eventually reaches a "root" that identifies the group. Two vertices are in the same group exactly when following their parent chains leads to the same root. Here is a working Python implementation, traced against our own six-town example:

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

def union(parent, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x == root_y:
        return False        # already connected -> would form a cycle
    parent[root_x] = root_y
    return True              # merged two separate groups

def kruskal(vertices, edges):
    # edges is a list of (weight, u, v) tuples
    parent = {v: v for v in vertices}
    mst, total_weight = [], 0
    for weight, u, v in sorted(edges):
        if union(parent, u, v):
            mst.append((u, v, weight))
            total_weight += weight
    return mst, total_weight

towns = ['A', 'B', 'C', 'D', 'E', 'F']
routes = [(4,'A','B'), (8,'A','C'), (3,'B','C'), (7,'B','D'),
          (2,'C','D'), (5,'C','E'), (6,'D','E'), (9,'D','F'), (1,'E','F')]

tree, cost = kruskal(towns, routes)
print(tree)   # [('E','F',1), ('C','D',2), ('B','C',3), ('A','B',4), ('C','E',5)]
print(cost)   # 15

Trace it by hand and you will land on exactly the same five edges and the same total, 15, that we found manually above — sorting guarantees the algorithm always looks at the cheapest untested edge first, and the union–find check guarantees it never wastes money closing a cycle.

Prim's Algorithm: grow one tree outward from a single seed

Kruskal's algorithm thinks in terms of the whole edge list at once. Prim's algorithm thinks differently: start from a single vertex, and repeatedly grow the tree by attaching whichever unattached vertex is reachable most cheaply from the tree built so far — never looking at edges that lie entirely outside the current tree.

Start Prim's algorithm at town A:

1. Tree = {A}. Edges leaving the tree: A–B(4), A–C(8). Cheapest is A–B. Add B. Tree = {A,B}, cost so far = 4.
2. Edges leaving {A,B}: A–C(8), B–C(3), B–D(7). Cheapest is B–C. Add C. Tree = {A,B,C}, cost = 7.
3. Edges leaving {A,B,C}: A–C is now internal (ignore), B–D(7), C–D(2), C–E(5). Cheapest is C–D. Add D. Tree = {A,B,C,D}, cost = 9.
4. Edges leaving {A,B,C,D}: B–D internal (ignore), C–E(5), D–E(6), D–F(9). Cheapest is C–E. Add E. Tree = {A,B,C,D,E}, cost = 14.
5. Edges leaving the tree: D–E internal (ignore), E–F(1), D–F(9). Cheapest is E–F. Add F. Tree = {A,B,C,D,E,F}, cost = 15. All towns connected — stop.

Prim's algorithm, started from a completely different vertex and reasoning edge-by-frontier rather than sorting the whole list up front, still lands on exactly the same five edges — A–B, B–C, C–D, C–E, E–F — and the same total, ₹15 lakh. That is not a coincidence, and the next section explains why.

A computer implements Prim's "always grab the cheapest edge on the frontier" step efficiently using a min-heap (priority queue), which keeps the cheapest available edge at the top without having to rescan every edge each round:

import heapq

def prim(vertices, adj, start):
    visited = {start}
    frontier = [(w, start, v) for v, w in adj[start]]
    heapq.heapify(frontier)
    mst, total_weight = [], 0
    while frontier and len(visited) < len(vertices):
        weight, u, v = heapq.heappop(frontier)
        if v in visited:
            continue                      # would form a cycle -- skip
        visited.add(v)
        mst.append((u, v, weight))
        total_weight += weight
        for next_v, w in adj[v]:
            if next_v not in visited:
                heapq.heappush(frontier, (w, v, next_v))
    return mst, total_weight

adj = {
    'A': [('B',4), ('C',8)],
    'B': [('A',4), ('C',3), ('D',7)],
    'C': [('A',8), ('B',3), ('D',2), ('E',5)],
    'D': [('B',7), ('C',2), ('E',6), ('F',9)],
    'E': [('C',5), ('D',6), ('F',1)],
    'F': [('D',9), ('E',1)],
}

tree, cost = prim(['A','B','C','D','E','F'], adj, 'A')
print(tree)   # [('A','B',4), ('B','C',3), ('C','D',2), ('C','E',5), ('E','F',1)]
print(cost)   # 15

Running this trace line by line: the heap starts with A's two edges, always pops the smallest weight, skips any edge that leads to an already-visited town (that would be a cycle), and pushes fresh edges from every newly added town. You get the identical five edges and total cost of 15 that both the hand trace and Kruskal's code produced.

Why greedy choices are allowed to work here

It can feel suspicious that simply grabbing the cheapest available edge, over and over, with no backtracking, actually produces the globally cheapest tree. Greedy strategies fail for plenty of other problems, so why does it succeed here? The reason is a fact called the cut property: if you split all the vertices of a graph into any two non-empty groups, the single cheapest edge that crosses between the two groups is guaranteed to belong to some minimum spanning tree.

Here is the intuition, not a formal proof. Suppose you built a spanning tree that skipped that cheapest crossing edge. Because your tree is still connected, it must use some other edge to link the two groups — and by assumption, that other edge costs at least as much as the cheapest one. Swap the expensive crossing edge out and the cheap one in. The result is still a valid spanning tree (it still connects both groups, and removing the expensive edge cannot create a disconnection because the new cheap edge already reconnects them), and it costs no more than before. So there is never a reason to prefer the expensive crossing edge over the cheapest one.

Apply this to town E in our example: split the vertices into {E} and everything else. The cheapest edge touching E is E–F at ₹1 lakh (compare to C–E at ₹5 lakh). The cut property guarantees E–F belongs in the MST — exactly what both algorithms found. Kruskal's algorithm effectively applies this reasoning globally, sorted cheapest-first; Prim's applies it locally, one growing frontier at a time. Different bookkeeping, same guarantee, same answer.

One detail worth naming precisely: this example has nine distinct edge weights, no two routes tied in cost. When all weights are distinct, the Minimum Spanning Tree is unique — there is exactly one cheapest way to connect everyone, which is why Kruskal's and Prim's, despite working completely differently, were guaranteed to agree. If two or more edges shared the same weight, there could be several different trees that all achieve the same minimum total cost, and which one a particular algorithm returns would depend on how it breaks ties.

Common misconception: "the MST gives the shortest route between any two towns"

This is the single most common confusion students carry out of this topic, and it is worth correcting carefully, because on the surface an MST does look like it should also hand you the fastest way to get from any one vertex to any other. It does not, and the difference matters enough that a different algorithm (Dijkstra's shortest path algorithm, covered separately) exists specifically to solve the shortest-route problem.

Consider a small four-town example: S, A, B, T, with roads S–A (₹1 lakh), A–B (₹1 lakh), B–T (₹1 lakh), and a direct shortcut S–T (₹2 lakh). Because connecting all four towns needs only 3 edges (n − 1 = 3), and the path S–A–B–T already achieves that for a total of ₹3 lakh, the Minimum Spanning Tree is exactly those three edges — the direct S–T shortcut is left out entirely, since including it while still reaching A and B would cost more overall, not less.

Now ask: what is the cheapest way to travel specifically from S to T? Inside the MST, the only route from S to T is the long way round, S→A→B→T, costing 1+1+1 = ₹3 lakh. But the direct edge S–T, which the MST didn't build at all, costs only ₹2 lakh — a full ₹1 lakh cheaper for that one specific journey. The Minimum Spanning Tree minimises the total cost of connecting every town to every other town at least once; it makes no promise whatsoever about the cheapest way to get between any one particular pair. A courier company deciding the fastest route between two specific hubs should reach for a shortest-path algorithm, not an MST — the two problems, despite looking similar, optimise for genuinely different things.

How much work do these algorithms actually do?

For a graph with V vertices and E edges, Kruskal's algorithm spends most of its effort sorting the edge list, which takes on the order of E log E comparisons; after that, each union–find check is extremely fast (close to constant time in practice), so the whole algorithm scales as roughly E log E. Prim's algorithm, implemented with a min-heap as in the code above, does roughly E log V work, since every edge can be pushed onto the heap once and every heap operation costs about log V. For the kind of sparse, spread-out networks that real infrastructure planning deals with — where towns connect to a handful of nearby neighbours rather than to everyone — both algorithms comfortably handle graphs with tens of thousands of vertices in a fraction of a second, which is precisely why they are the standard tools for this kind of network design rather than checking every possible spanning tree by brute force (a number that explodes far too fast to ever compute directly for large graphs).

Where this idea actually gets used

The exact optimisation this chapter walks through — connect every point in a set at the lowest total cost, with no cycles allowed — is the mathematical backbone of infrastructure planning whenever a network has to be built rather than merely used: telecom companies deciding which stretches of fibre or copper to lay between exchanges, power utilities choosing which transmission lines to build between substations, and municipal planners routing water or sewage pipelines between neighbourhoods all face a version of this same problem, weighted by construction distance, terrain difficulty, or material cost. It also shows up outside civil infrastructure: in data analysis, a technique called single-linkage hierarchical clustering groups similar data points together by repeatedly merging the two closest clusters — which is structurally the same greedy, cycle-avoiding merge process as Kruskal's algorithm, just applied to "similarity" instead of "cable cost."

Check your understanding

Work through these before checking the answers that follow each one.

1. Edge count. A network planner is connecting 12 substations with the minimum number of transmission lines needed to reach everyone, with no redundant loops. How many lines will the final network contain?
Answer: n − 1 = 11 lines, by the spanning-tree edge-count rule.

2. Trace it yourself. Five towns P, Q, R, S, T are connected by roads: P–Q(₹2L), Q–R(₹1L), P–R(₹6L), Q–S(₹5L), R–S(₹4L), S–T(₹3L), R–T(₹7L). Run Kruskal's algorithm by hand and find the total cost of the MST.
Answer: Sorted order is Q–R(1), P–Q(2), S–T(3), R–S(4), Q–S(5), P–R(6), R–T(7). Accept Q–R (groups {Q,R}); accept P–Q (groups {P,Q,R}); accept S–T (groups {S,T}); accept R–S, which merges {P,Q,R} and {S,T} into one group of all five towns — that's 4 edges for 5 vertices, done. Total = 1+2+3+4 = ₹10 lakh. (Q–S, P–R, and R–T are all rejected as cycle-formers.)

3. Conceptual. Two students run Kruskal's algorithm on the same weighted graph, but one of them breaks ties between equal-weight edges by processing them in a different order than the other. Could they legitimately end up choosing a different set of edges, yet both still be correct?
Answer: Yes — when a graph has two or more edges of equal weight, more than one spanning tree can achieve the same minimum total cost. Both students would be correct as long as their final totals match, even if the specific edges differ.

4. Spot the error. A student claims: "Once I've built the MST rooted from town A, the path inside that tree from A to any other town is automatically the cheapest possible route between them." Is this true?
Answer: No. As the S–A–B–T versus direct S–T example showed, the MST minimises total network-building cost, not any single point-to-point distance. The cheapest route between two specific towns can use edges the MST never built.

Summary

• A spanning tree connects every vertex of a graph using exactly n − 1 edges and contains no cycles; a graph generally has many possible spanning trees.
• The Minimum Spanning Tree is the spanning tree whose total edge weight is smallest — the cheapest way to keep every vertex reachable from every other.
• Kruskal's algorithm sorts all edges by weight and greedily accepts each one unless it would close a cycle, checked efficiently with a union–find structure.
• Prim's algorithm grows a single tree outward from a starting vertex, always attaching the cheapest edge available on the current frontier, efficiently tracked with a min-heap.
• Both algorithms are greedy yet provably correct, because of the cut property: the cheapest edge crossing any split of the vertices into two groups always belongs to some MST.
• When all edge weights are distinct, the MST is unique, which is why Kruskal's and Prim's — despite working completely differently — landed on the identical five edges in this chapter's example.
• An MST minimises total connection cost across the whole network — it does not give the shortest route between any one specific pair of vertices; that is a different problem, solved by shortest-path algorithms such as Dijkstra's.

Think About It

Think about this: How would you explain minimum spanning trees: connecting networks efficiently to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.