9.21 Minimum Spanning Trees

Problem

You need to connect all vertices in a graph while minimizing total cost.

Many real-world systems involve building networks:

Connecting cities with roads
Connecting offices with fiber cables
Connecting servers with network links
Connecting power stations with transmission lines
Connecting sensors with communication channels

Each connection has a cost.

You want a network that:

Connects every vertex.
Uses the minimum possible total cost.
Avoids unnecessary redundancy.

Solution

Compute a Minimum Spanning Tree (MST).

A spanning tree is a subgraph that:

Contains every vertex.
Is connected.
Contains no cycles.

A minimum spanning tree is a spanning tree whose total edge weight is as small as possible.

Consider:

      4
  A ----- B
  | \     |
1 |  \2   | 5
  |   \   |
  |    \  |
  C ----- D
      3

Possible spanning tree:

A -- C (1)
A -- D (2)
C -- D (3)

This contains a cycle and therefore is not a tree.

Valid MST:

A -- C (1)
A -- D (2)
A -- B (4)

Total cost:

1 + 2 + 4 = 7

Discussion

A spanning tree contains exactly:

V - 1

edges.

This is a fundamental property.

If fewer edges exist:

Graph disconnected

If more edges exist:

Cycle exists

Therefore every spanning tree of a graph with:

V vertices

contains exactly:

V - 1 edges

The MST problem asks:

Which V - 1 edges produce the smallest cost?

Why Cycles Matter

Consider:

A -- B (2)
|    |
4    3
|    |
C -- D (1)

Suppose all four edges are selected.

A cycle appears.

Removing the most expensive edge:

A -- C (4)

keeps the graph connected while reducing cost.

This observation is central to MST algorithms.

Cycles are wasteful because at least one edge can be removed without disconnecting the graph.

Example MST

Graph:

      7
  A ----- B
  |       |
2 |       | 3
  |       |
  C ----- D
      1

Possible spanning trees:

Tree 1

A-C
C-D
D-B

Cost:

2 + 1 + 3 = 6

Tree 2

A-B
A-C
C-D

Cost:

7 + 2 + 1 = 10

Tree 1 is better.

Therefore:

MST cost = 6

Greedy Structure

One remarkable property of MSTs is that greedy algorithms work.

Most optimization problems require global reasoning.

MSTs have special mathematical properties that allow local decisions to lead to globally optimal solutions.

Two famous algorithms exploit this:

Kruskal's algorithm
Prim's algorithm

Both produce optimal MSTs.

Kruskal's Algorithm

Kruskal's algorithm processes edges in increasing weight order.

Steps:

Sort edges by weight.
Add the smallest edge.
Skip edges that create cycles.
Continue until V - 1 edges have been chosen.

Example:

A-B = 1
B-C = 2
A-C = 5

Process:

Add A-B
Add B-C
Skip A-C

because:

A-C

would create a cycle.

Result:

Cost = 3

Union-Find for Cycle Detection

Kruskal's algorithm needs efficient cycle detection.

Union-Find is the standard solution.

Initially:

A
B
C
D

are separate sets.

When edge:

A-B

is added:

union(A, B)

When processing:

A-C

check:

find(A)
find(C)

If both vertices already belong to the same set, adding the edge would create a cycle.

Skip it.

Otherwise merge the sets.

Recipe: Union-Find

class UnionFind:
    def __init__(self, vertices):
        self.parent = {
            v: v
            for v in vertices
        }

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

        return x

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return False

        self.parent[root_b] = root_a

        return True

This simplified implementation is sufficient for understanding Kruskal's algorithm.

Recipe: Kruskal's Algorithm

def kruskal(vertices, edges):
    uf = UnionFind(vertices)

    mst = []

    edges = sorted(
        edges,
        key=lambda edge: edge[2]
    )

    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append(
                (u, v, weight)
            )

    return mst

Example:

vertices = [
    "A",
    "B",
    "C",
]

edges = [
    ("A", "B", 1),
    ("B", "C", 2),
    ("A", "C", 5),
]

Output:

[
    ("A", "B", 1),
    ("B", "C", 2),
]

Prim's Algorithm

Prim's algorithm grows the tree from a starting vertex.

Instead of processing all edges globally, it repeatedly expands the current tree.

Example:

Start at A

Choose cheapest outgoing edge

Repeat

This resembles Dijkstra's algorithm.

The difference is that MSTs optimize total tree cost rather than shortest-path distances.

Prim Example

Graph:

A-B = 1
A-C = 4
B-C = 2

Start:

Choose:

A-B = 1

Current tree:

A-B

Next cheapest edge leaving the tree:

B-C = 2

Final MST:

A-B
B-C

Cost:

Recipe: Prim's Algorithm

import heapq

def prim(graph, start):
    visited = {start}

    heap = []

    for neighbor, weight in graph[start]:
        heapq.heappush(
            heap,
            (weight, start, neighbor)
        )

    mst = []

    while heap:
        weight, u, v = heapq.heappop(heap)

        if v in visited:
            continue

        visited.add(v)

        mst.append((u, v, weight))

        for neighbor, w in graph[v]:
            if neighbor not in visited:
                heapq.heappush(
                    heap,
                    (w, v, neighbor)
                )

    return mst

This implementation uses a priority queue to repeatedly select the cheapest expansion edge.

Cut Property

The correctness of MST algorithms relies on the cut property.

Suppose the graph is divided into two groups:

Left
Right

Any edge crossing between them belongs to a cut.

The cut property states:

The minimum-weight edge crossing a cut is always safe to include in some MST.

This theorem explains why greedy selection works.

Both Kruskal and Prim repeatedly exploit this fact.

MST Is Not Unique

MSTs are not always unique.

Example:

A-B = 1
B-C = 1
A-C = 1

Any two edges form a valid MST.

Possible result:

A-B
B-C

or:

A-B
A-C

Both have cost:

Different algorithms may produce different but equally optimal trees.

Applications

Network Design

Connect offices using minimum cable cost.

Road Construction

Build roads connecting cities while minimizing budget.

Power Grids

Connect substations with minimal transmission infrastructure.

Clustering

Many clustering algorithms begin with an MST.

Image Processing

MSTs appear in segmentation and graph-based vision techniques.

Complexity Analysis

Let:

V = number of vertices
E = number of edges

Kruskal

Operation	Complexity
Edge sorting	O(E log E)
Union-Find operations	O(E α(V))
Total	O(E log E)

Prim (Heap Version)

Operation	Complexity
Priority queue operations	O(E log V)
Total	O(E log V)

Both are efficient enough for very large sparse graphs.

Common Pitfalls

Do not use MST algorithms on directed graphs.

The classical MST problem is defined for undirected weighted graphs.

Do not confuse MSTs with shortest-path trees.

An MST minimizes total tree cost.

A shortest-path tree minimizes distance from one source.

These objectives are different.

Do not forget that MSTs contain exactly:

V - 1 edges

Do not allow cycle-forming edges during construction.

Do not assume the MST is unique.

Equal-weight edges often produce multiple optimal solutions.

Shortest Path Tree vs MST

Consider:

      10
  A ------- B
   \       /
    \     /
   1 \   / 1
      \ /
       C

Shortest-path tree from A:

A-C
A-B

Cost:

MST:

A-C
C-B

Cost:

Different objectives lead to different trees.

This distinction is important.

Takeaway

A Minimum Spanning Tree connects all vertices using the smallest possible total edge weight while avoiding cycles. MSTs form the foundation of network design, infrastructure planning, clustering, and many optimization problems. Kruskal's algorithm grows the solution by selecting globally cheapest edges, while Prim's algorithm expands a single tree through locally cheapest connections. Both exploit the cut property and produce optimal solutions in polynomial time.