The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Minimum Spanning Trees

Next ►
►

In the previous lesson we minimized the cost of one route between two points. This lesson changes the question entirely: given a set of nodes that must all be connected to one another, which connections do we pick so the total cost is minimal? The answer is the minimum spanning tree (MST), a problem on undirected graphs that shows up whenever a network is being designed: wiring offices, laying fiber between sites, or — in the most "infrastructure-flavored" TaskFlow scenario of the whole course — deciding which coordination channels to keep between teams. We'll see the two classic algorithms, Prim (Dijkstra's first cousin, once again with heapq) and Kruskal, which will force us to build a delightful new auxiliary structure: Union-Find.

Contents

  1. What a minimum spanning tree is
  2. MST versus shortest paths: don't confuse them
  3. The example graph: coordinating TaskFlow's teams
  4. Prim: growing the tree from a vertex
  5. Kruskal: cheap edges first, without forming cycles
  6. Union-Find: the structure that makes Kruskal fast
  7. Kruskal trace
  8. Prim versus Kruskal

What a minimum spanning tree is

Given an undirected, weighted, connected graph, a spanning tree is a subgraph that:

  • includes all the vertices,
  • is connected (everything reachable from everything, possibly with stopovers),
  • is acyclic — and from lesson 07-01 we know "connected + acyclic" = tree, with exactly n − 1 edges.

Of all possible spanning trees, the minimum one has the smallest sum of weights. The intuition for why a tree suffices: if a selection of edges contains a cycle, you can remove the cycle's most expensive edge without disconnecting anything — so the optimal solution never has cycles.

Two important restrictions of the problem:

  • Undirected graphs only. "Connecting" is symmetric; on directed graphs the analogous problem (arborescences) is a different beast and we don't cover it.
  • Connected graphs only. If there are islands, no tree can span everything; in that case you compute a spanning forest, one MST per component (Kruskal does this for free, as we'll see).

MST versus shortest paths: don't confuse them

They are the two big optimization problems on weighted graphs and are easily confused:

Shortest paths (07-04) MST (this lesson)
Question Cheapest route from A to B? Cheapest network connecting everything?
Optimizes The cost of each route from the source The total cost of the chosen edges
Graph Directed or not Undirected
Result Shortest-path tree from one source Tree with no privileged source
Guarantee it does NOT give — The path between two nodes inside the MST may not be their shortest path

The last point is the treacherous one: inside the MST, getting from one node to another may require a detour more expensive than their direct shortest path in the original graph. The MST saves on the network's total bill, not on each individual trip.

The example graph: coordinating TaskFlow's teams

Five teams use TaskFlow: backend, frontend, data, qa, and design. Keeping a stable coordination channel between two teams (meetings, integrations, shared documentation) has a weekly cost in hours, different for each pair. We want information to be able to flow between any pair of teams (directly or through others) while paying the minimum total:

teams = Graph(directed=False)        # coordinating is symmetric
teams.add_edge("backend", "frontend", 4)
teams.add_edge("backend", "data", 2)
teams.add_edge("backend", "qa", 7)
teams.add_edge("data", "qa", 3)
teams.add_edge("frontend", "qa", 5)
teams.add_edge("frontend", "design", 1)
teams.add_edge("design", "qa", 6)
graph LR
    B[backend] ---|4| F[frontend]
    B ---|2| D[data]
    B ---|7| Q[qa]
    D ---|3| Q
    F ---|5| Q
    F ---|1| S[design]
    S ---|6| Q

With 5 vertices, the MST will have exactly 4 edges. Let's give away the solution up front so we can check both algorithms against it: frontend–design (1), backend–data (2), data–qa (3), and backend–frontend (4), total 10 hours per week.

Prim: growing the tree from a vertex

Prim builds the MST like a spreading oil stain: it starts at an arbitrary vertex and, at each step, adds the cheapest edge connecting the current tree to a vertex outside it. "The cheapest available"? heapq again:

import heapq

def prim(graph, start):
    """Returns (mst_edges, total_cost). Undirected, connected graph."""
    in_tree = {start}
    mst_edges = []
    total = 0
    # (weight, source, target): the heap orders by weight, as in Dijkstra
    heap = [(weight, start, target)
            for target, weight in graph.neighbors(start).items()]
    heapq.heapify(heap)                  # heap in O(n), module 6

    while heap and len(in_tree) < len(graph.vertices()):
        weight, source, target = heapq.heappop(heap)
        if target in in_tree:
            continue                     # stale edge: already inside
        in_tree.add(target)              # bring in the new vertex
        mst_edges.append((source, target, weight))
        total += weight
        for neighbor, w in graph.neighbors(target).items():
            if neighbor not in in_tree:  # the newcomer's offers
                heapq.heappush(heap, (w, target, neighbor))
    return mst_edges, total

edges, total = prim(teams, "backend")
print(edges)
# [('backend', 'data', 2), ('data', 'qa', 3), ('backend', 'frontend', 4),
#  ('frontend', 'design', 1)]
print(total)   # 10

If this code sounds familiar, it's because it is Dijkstra's skeleton with a single difference: the priority. Dijkstra orders the heap by accumulated distance from the source (dist + weight); Prim, by the loose edge's weight (weight). Dijkstra minimizes routes; Prim minimizes the connection bill. Same machinery, different question — it's worth comparing the two pieces of code side by side until you see the one-line difference.

Trace from backend (the oil stain):

Step Leaves the heap Accepted? Tree after the step Total
1 (2, backend, data) Yes {backend, data} 2
2 (3, data, qa) Yes + qa 5
3 (4, backend, frontend) Yes + frontend 9
4 (1, frontend, design) Yes + design: tree complete 10

Look at step 4: when frontend joins, its cheap edge to design (weight 1) enters the heap and jumps ahead of the expensive pending offers — (5, frontend, qa), (6, qa, design), and (7, backend, qa) stay inside without ever surfacing, because with all 5 vertices in, the loop ends.

Cost: O(a · log n), like Dijkstra.

Kruskal: cheap edges first, without forming cycles

Kruskal attacks from the other flank: it sorts all edges from lightest to heaviest (here the edge list mentioned in 07-02 shines) and accepts them one by one, with a single rule: reject any edge whose two endpoints are already connected (it would form a cycle). It stops after accepting n − 1.

The difficulty lies in the rule: "are u and v already connected?" must be answered thousands of times, very fast. BFS per query? O(n + a) each time: too much. The answer is a new structure.

Union-Find: the structure that makes Kruskal fast

Union-Find (or disjoint sets) maintains a collection of sets that only know how to do two things, both in nearly O(1):

  • find(x): what is the representative of x's set? (two elements are connected if they share a representative),
  • union(x, y): merge the sets of x and y.

The implementation is surprisingly small: each element points to a "parent" and the representative is the root of that chain — internally it's a forest of little trees, one more nod to module 6. Two optimizations make it fly:

  • Path compression: while looking for the root, re-hook every visited node directly onto it; the next lookup will be nearly instant.
  • Union by rank: when merging, the tree with the smaller estimated height (rank) hangs from the taller one, avoiding long chains.
class UnionFind:
    def __init__(self, elements):
        self.parent = {x: x for x in elements}   # each its own root
        self.rank = {x: 0 for x in elements}

    def find(self, x):
        root = x
        while self.parent[root] != root:         # climb to the root
            root = self.parent[root]
        while self.parent[x] != root:            # path compression:
            self.parent[x], x = root, self.parent[x]   # re-hook straight to the root
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                         # already connected
        if self.rank[rx] < self.rank[ry]:        # union by rank:
            rx, ry = ry, rx                      # rx becomes the taller one
        self.parent[ry] = rx                     # the short one hangs from the tall one
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1                   # only grows on a tie
        return True

With both optimizations, a sequence of operations costs in practice nearly constant time per operation (technically O(α(n)), where α is the inverse Ackermann function: ≤ 4 for any conceivable n). Note the design detail: union returns False if the elements were already connected — exactly Kruskal's question, answered as a side effect.

def kruskal(graph):
    edges = sorted(                          # edge list ordered by weight
        {tuple(sorted((u, v))) + (w,)        # (u, v, w) without u-v / v-u duplicates
         for u in graph.vertices()
         for v, w in graph.neighbors(u).items()},
        key=lambda e: e[2])
    uf = UnionFind(graph.vertices())
    mst, total = [], 0
    for u, v, w in edges:
        if uf.union(u, v):                   # False = would form a cycle: skip
            mst.append((u, v, w))
            total += w
            if len(mst) == len(graph.vertices()) - 1:
                break                        # tree complete: n - 1 edges
    return mst, total

print(kruskal(teams))
# ([('design', 'frontend', 1), ('backend', 'data', 2), ('data', 'qa', 3),
#   ('backend', 'frontend', 4)], 10)

A note on how edges is built: since the undirected graph stores every edge in both directions, tuple(sorted((u, v))) normalizes the pair and the set removes the duplicate. Kruskal's total cost: O(a · log a), dominated by the sort.

Kruskal trace

Sorted edges: (design–frontend, 1), (backend–data, 2), (data–qa, 3), (backend–frontend, 4), (frontend–qa, 5), (design–qa, 6), (backend–qa, 7).

Edge Endpoints already connected? Decision Sets after the step
design–frontend (1) No Accept {design, frontend} {backend} {data} {qa}
backend–data (2) No Accept {design, frontend} {backend, data} {qa}
data–qa (3) No Accept {design, frontend} {backend, data, qa}
backend–frontend (4) No Accept → 4 edges: done {everyone}
frontend–qa (5) (never gets evaluated) — —

Same tree and same total (10) as Prim — as it should be: when no weights repeat, the MST is unique. Notice the difference in style: Prim maintains one growing tree; Kruskal maintains a forest of fragments that keep merging (which is why, on a disconnected graph, Kruskal ends up with one MST per island without changing a single line).

Prim versus Kruskal

Prim Kruskal
Strategy Grow a tree from a vertex Accept globally cheap edges
Supporting structure heapq (module 4) Sorting + Union-Find
Cost O(a · log n) O(a · log a)
Comfortable when... Dense graph, adjacency list Sparse graph, edges already as a list
Disconnected graph Only covers the starting component Gives the whole forest for free
Resembles Dijkstra (swap the priority) A greedy filter over sorted edges

Both are greedy algorithms: at every step they take the locally cheapest option and, for this problem — unlike so many others — that provably leads to the global optimum.

Common Mistakes and Tips

  • Applying MST to a directed graph. The problem is defined for undirected graphs; build the graph with Graph(directed=False) or the algorithms will produce nonsense.
  • Confusing the MST with shortest paths and using Prim's tree to answer "cheapest route from A to B?". Revisit the table in section 2: they optimize different things.
  • Forgetting the stale-edge continue in Prim: you'd accept edges to vertices already in the tree, creating cycles and overcounting cost.
  • Implementing Union-Find without compression or rank. It works, but the internal trees degenerate into chains and find becomes O(n) — the same degeneration the unbalanced BST suffered in module 6.
  • Duplicating edges in Kruskal when extracting them from an undirected graph (u–v and v–u): either normalize as we did, or the algorithm evaluates everything twice (it doesn't break the result, but it betrays sloppiness).
  • Tip: Union-Find is worth far more than Kruskal alone: dynamic connectivity, on-the-fly cycle detection, clustering... In the final exercises (07-07), the BFS alternative for connected components will help you appreciate when each one shines.

Exercises

Exercise 1: MST by hand

Add a sixth team: mobile, with edges mobile–frontend (2) and mobile–qa (4). Compute the new MST with Kruskal by hand (decision table) and its total cost.

Exercise 2: the MST's detour

In the lesson's MST, what is the path between design and qa and how much does it cost, adding up its edges? Compare it with the direct edge design–qa (6) and explain why the MST "prefers" the detour.

Exercise 3: Union-Find as a cycle detector

Using only UnionFind (no DFS), write has_undirected_cycle(edges, vertices) that detects whether an undirected graph given as an edge list contains a cycle. Hint: what does it mean when union returns False?

Solutions

Solution 1: Sorted edges: 1 (design–frontend), 2 (backend–data), 2 (mobile–frontend), 3 (data–qa), 4 (backend–frontend), 4 (mobile–qa), 5, 6, 7. Decisions: accept 1, 2, 2, 3, 4 (backend–frontend joins {design, frontend, mobile} with {backend, data, qa}); with 5 edges for 6 vertices, done. mobile–qa (4) is never evaluated (connected via frontend...backend...qa). Total: 1 + 2 + 2 + 3 + 4 = 12.

Solution 2: In the MST, from design to qa you travel design–frontend–backend–data–qa: 1 + 4 + 2 + 3 = 10, against 6 for the direct edge. The MST discarded design–qa because by the time its turn came, its endpoints were already connected: for the network's total bill that edge was redundant. It's the practical proof of section 2's warning: the MST doesn't promise good individual trips, only the cheapest complete network.

Solution 3:

def has_undirected_cycle(edges, vertices):
    uf = UnionFind(vertices)
    for u, v in edges:
        if not uf.union(u, v):   # already connected: this edge closes a cycle
            return True
    return False

print(has_undirected_cycle(
    [("a", "b"), ("b", "c")], ["a", "b", "c"]))          # False
print(has_undirected_cycle(
    [("a", "b"), ("b", "c"), ("c", "a")], ["a", "b", "c"]))  # True

If union returns False, the endpoints already shared a set: a path existed between them and the new edge closes it into a cycle. It's the course's third cycle-detection technique (Floyd on lists, white/gray/black on directed graphs, Union-Find on undirected ones), each on its own turf.

Conclusion

The MST answers a different question than shortest paths — minimize the total network, not each trip — and lives only on undirected graphs. Prim builds it like an oil stain with the usual heapq (one line away from Dijkstra); Kruskal sorts the edges and filters out cycles with Union-Find, the new auxiliary structure that, with path compression and union by rank, answers "are these connected?" in nearly constant time. With this, the module's toolbox is complete: traversals, cycles, orderings, paths, and networks. The next lesson adds no new algorithm: it puts all of them to work together — TaskFlow's full scheduler (order, cycles, parallelism, and the critical path), social-network-style collaborator suggestions, and even a miniature PageRank.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved