Minimum Spanning Trees

Introduction

A Minimum Spanning Tree (MST) is a spanning tree of a weighted graph with the minimum possible total edge weight. MSTs are crucial in network optimization, circuit design, and many real-world applications.

Definition

Given a connected, weighted, undirected graph G = (V, E) with weight function w: E → ℝ, a minimum spanning tree is a spanning tree T such that:

w(T) = Σ w(e) for all e in T is minimized

In simple terms: Connect all vertices with minimum total cost.

Example: Basic MST

Weighted Graph:

      2
  1-----2
  |\ 3/|
 4| X |5
  |/ \|
  3---4
      6

Edges: (1,2,2), (1,3,4), (2,3,3), (2,4,5), (3,4,6)

MST:

    2
1-----2
|    /
|3  /
| /
3   4

Edges: (1,2,2), (2,3,3), (2,4,5) Total weight: 2 + 3 + 5 = 10

Properties of MST

Property 1: Unique MST

If all edge weights are distinct, the MST is unique.

If weights can be equal, multiple MSTs may exist with same total weight.

Property 2: Cut Property

For any cut (partition of vertices into two sets), the minimum weight edge crossing the cut is in some MST.

Use: Justifies correctness of greedy algorithms.

Property 3: Cycle Property

For any cycle, the maximum weight edge in that cycle is NOT in any MST (assuming distinct weights).

Use: Can remove expensive edges.

Property 4: Edge Count

MST always has exactly (n-1) edges for n vertices.

Algorithms for Finding MST

1. Kruskal’s Algorithm

Strategy: Build MST by adding edges in order of increasing weight, skipping those that create cycles.

Algorithm:

Kruskal(Graph G):
    Sort all edges by weight (ascending)
    MST = empty set

    for each edge (u,v) in sorted order:
        if adding (u,v) doesn't create cycle:
            add (u,v) to MST

    return MST

Cycle Detection: Use Union-Find (Disjoint Set) data structure

Time Complexity: O(E log E) or O(E log V)

• Sorting edges: O(E log E)
• Union-Find operations: O(E α(V)) ≈ O(E)
• Total: O(E log E)

Kruskal’s Example

Graph:

      2
  1-----2
  |\ 4/|
 5| X |3
  |/ \|
  3---4
      6

Edges: (1,2,2), (2,4,3), (2,3,4), (1,3,5), (3,4,6)

Steps:

Step 1: Sort edges: 2, 3, 4, 5, 6

Step 2: Process edges:

1. Add (1,2,2): MST = {(1,2)}
2. Add (2,4,3): MST = {(1,2), (2,4)}
3. Add (2,3,4): MST = {(1,2), (2,4), (2,3)}
4. Skip (1,3,5): Would create cycle 1-2-3-1
5. Skip (3,4,6): Would create cycle 2-3-4-2

MST edges: {(1,2), (2,4), (2,3)} Total weight: 2 + 3 + 4 = 9

Kruskal’s with Union-Find

Data Structure:

• Each vertex initially in its own set
• Union: Merge two sets
• Find: Determine which set a vertex belongs to

Pseudocode:

Kruskal(G):
    for each vertex v:
        MakeSet(v)

    Sort edges by weight
    MST = empty

    for each edge (u,v,w) in sorted order:
        if Find(u) ≠ Find(v):
            MST.add((u,v,w))
            Union(u,v)

    return MST

2. Prim’s Algorithm

Strategy: Grow MST from a starting vertex, always adding the minimum weight edge that connects tree to a non-tree vertex.

Algorithm:

Prim(Graph G, start vertex s):
    MST = empty
    visited = {s}
    PQ = priority queue of all edges from s

    while visited ≠ V and PQ not empty:
        (u,v,w) = PQ.extractMin()

        if v not in visited:
            add (u,v) to MST
            add v to visited
            add all edges from v to PQ

    return MST

Time Complexity:

• With binary heap: O(E log V)
• With Fibonacci heap: O(E + V log V)

Prim’s Example

Graph:

      2
  1-----2
  |\ 4/|
 5| X |3
  |/ \|
  3---4
      6

Start from vertex 1:

Step 1: Visited = {1}, Edges from 1: (1,2,2), (1,3,5)

• Add minimum: (1,2,2)

Step 2: Visited = {1,2}, New edges: (2,4,3), (2,3,4)

• Add minimum: (2,4,3)

Step 3: Visited = {1,2,4}, New edge: (4,3,6)

• Edges available: (2,3,4), (1,3,5), (4,3,6)
• Add minimum: (2,3,4)

Step 4: Visited = {1,2,4,3}, All vertices visited

MST: {(1,2,2), (2,4,3), (2,3,4)} Total: 9

Prim’s with Priority Queue

Pseudocode:

Prim(G, start):
    for each vertex v:
        key[v] = ∞
        parent[v] = NULL

    key[start] = 0
    PQ = all vertices (keyed by key[])

    while PQ not empty:
        u = PQ.extractMin()

        for each neighbor v of u:
            if v in PQ and w(u,v) < key[v]:
                parent[v] = u
                key[v] = w(u,v)
                PQ.decreaseKey(v)

    return MST from parent array

Comparison: Kruskal vs Prim

When to Use Which?

Kruskal’s:

• Sparse graphs (fewer edges)
• When edges are pre-sorted
• Simpler to understand

Prim’s:

• Dense graphs (many edges)
• When starting vertex matters
• Better for adjacency matrix

Another Algorithm: Borůvka’s Algorithm

Strategy: For each component, add the cheapest outgoing edge. Repeat until one component.

Steps:

1. Each vertex is its own component
2. For each component, find minimum weight edge leaving it
3. Add all such edges to MST
4. Merge components
5. Repeat until one component

Time Complexity: O(E log V)

Historical Note: Oldest MST algorithm (1926)!

Detailed Example: Step-by-Step Kruskal

Graph:

      7        5
  A-----B---------C
  |    / \        |
 8|  /4   \3      |9
  | /      \      |
  D--------E------F
      6        2

Edges sorted by weight:

1. (E,F,2)
2. (B,E,3)
3. (B,D,4)
4. (B,C,5)
5. (D,E,6)
6. (A,B,7)
7. (A,D,8)
8. (C,F,9)

Kruskal’s Execution:

Initially: Each vertex in own set

• Sets: {A}, {B}, {C}, {D}, {E}, {F}

Step 1: Add (E,F,2)

• MST = {(E,F,2)}
• Sets: {A}, {B}, {C}, {D}, {E,F}

Step 2: Add (B,E,3)

• MST = {(E,F,2), (B,E,3)}
• Sets: {A}, {B,E,F}, {C}, {D}

Step 3: Add (B,D,4)

• MST = {(E,F,2), (B,E,3), (B,D,4)}
• Sets: {A}, {B,D,E,F}, {C}

Step 4: Add (B,C,5)

• MST = {(E,F,2), (B,E,3), (B,D,4), (B,C,5)}
• Sets: {A}, {B,C,D,E,F}

Step 5: Skip (D,E,6) - would create cycle

Step 6: Add (A,B,7)

• MST = {(E,F,2), (B,E,3), (B,D,4), (B,C,5), (A,B,7)}
• Sets: {A,B,C,D,E,F}

Done! All vertices connected.

MST Weight: 2 + 3 + 4 + 5 + 7 = 21

Applications of MST

1. Network Design

Problem: Connect n cities with minimum total cable length

Solution: Build road/cable network as MST

Example:

• Internet backbone
• Electrical grid
• Water supply network

2. Approximation Algorithms

Traveling Salesman Problem (TSP):

• MST provides 2-approximation
• Tour cost ≤ 2 × MST cost

3. Cluster Analysis

Problem: Group similar data points

Solution:

1. Build MST of data points
2. Remove k-1 longest edges
3. Get k clusters

4. Image Segmentation

Problem: Partition image into regions

Solution:

• Pixels as vertices
• Similarity as edge weights
• MST helps find boundaries

5. Handwriting Recognition

Problem: Recognize connected components

Solution: MST identifies stroke structure

Proof of Correctness

Cut Property Proof

Claim: Minimum weight edge crossing any cut is in some MST.

Proof:

1. Let (u,v) be minimum edge crossing cut (S, V-S)
2. Suppose (u,v) not in MST T
3. Adding (u,v) to T creates cycle
4. Cycle must have another edge (x,y) crossing cut
5. w(u,v) ≤ w(x,y) (minimum crossing edge)
6. Replace (x,y) with (u,v) → weight doesn’t increase
7. New tree is also MST containing (u,v) ✓

Key Points for Exams

1. MST: spanning tree with minimum total edge weight
2. Kruskal’s: sort edges, add if no cycle (O(E log E))
3. Prim’s: grow tree from start vertex (O(E log V))
4. Both are greedy algorithms
5. Union-Find used in Kruskal’s for cycle detection
6. Priority queue used in Prim’s
7. Unique MST if all edge weights distinct
8. n vertices → (n-1) edges in MST
9. Cut property: min crossing edge in some MST
10. Applications: network design, clustering, TSP approximation

Practice Problems

1. Find MST using Kruskal’s:

    3
A-----B
|\   /|
|2\ /4|
|  X  |5
| /3\ |
|/   \|
C-----D
    6

2. What is total weight of MST for above graph?

3. How many edges in MST of graph with 10 vertices?

4. Apply Prim’s algorithm starting from A on above graph.

5. If all edge weights are doubled, how does MST change?

6. True or False: Removing the heaviest edge always gives MST.

7. Why does Kruskal’s use Union-Find?

8. For complete graph K₄ with all edges weight 1, how many MSTs?

9. Can disconnected graph have MST? Explain.

10. What’s time complexity of Kruskal’s and Prim’s?