Minimum Spanning Tree (MST)

What is a Spanning Tree?

Given a connected, undirected graph G with V vertices and E edges, a spanning tree is a subset of edges that:

1. Connects all V vertices (spans the graph)
2. Contains exactly V-1 edges
3. Has no cycles (it is a tree)

Think of it this way: a spanning tree is the minimal set of edges needed to keep everyone connected. Remove any edge and the tree disconnects. Add any edge and you create a cycle.

What is a Minimum Spanning Tree?

For a weighted graph, the minimum spanning tree is the spanning tree whose total edge weight is minimized. Among all possible spanning trees of a graph, the MST has the smallest sum of edge weights.

Why MST Matters

The MST problem appears whenever you need to connect a set of points at minimum cost:

• Network cabling: Connect offices with minimum total cable length
• Road construction: Connect villages with minimum total road
• Circuit design: Connect components with minimum wire
• Cluster analysis: Remove heaviest edges from MST to get clusters
• Approximation algorithms: MST gives 2-approximation for Traveling Salesman Problem

The Cut Property (Why Greedy Works)

The cut property is the theoretical foundation that makes greedy MST algorithms correct:

For any cut of the graph (partition of vertices into two non-empty sets), the minimum-weight edge crossing the cut MUST be in the MST.

A cut divides vertices into two groups S and V\\S. Edges crossing the cut have one endpoint in each group. The lightest such edge is safe to include in the MST.

Properties of MST

1. Uniqueness: If all edge weights are distinct, the MST is unique. If some weights are equal, multiple MSTs may exist (all with the same total weight).

1. Cycle Property: The maximum-weight edge in any cycle is NOT in the MST (if weights are distinct).

1. Edge count: An MST of V vertices always has exactly V-1 edges.

1. Substructure: If you remove any edge from the MST, the two resulting subtrees are themselves MSTs of the subgraphs they span.

MST Algorithms Overview

Two classic algorithms find the MST:

Kruskal's Algorithm (Edge-centric)

• Sort all edges by weight
• Greedily add edges that don't create cycles
• Uses Union-Find to detect cycles efficiently
• Best for sparse graphs: O(E log E)

Prim's Algorithm (Vertex-centric)

• Grow a tree from a starting vertex
• Always add the minimum-weight edge connecting tree to non-tree vertex
• Uses priority queue
• Best for dense graphs: O(E log V) with binary heap

Both are greedy and both produce correct MSTs thanks to the cut property.

Simple Example: Building a Network

MST vs Shortest Path

MST and shortest path solve fundamentally different problems:

• Shortest path: Minimum cost to travel from A to B
• MST: Minimum total cost to connect ALL vertices

An MST does NOT guarantee shortest paths between vertices. The path from A to B in the MST might be longer than the direct edge (if that edge was not included in the MST).

Time Complexity Comparison