Minimum Spanning Tree
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a spanning subgraph that connects all vertices with the minimum possible total edge weight, containing exactly V-1 edges for V vertices and no cycles. The MST is not necessarily unique if multiple edges have equal weights. MSTs are used in network design (telecom, power grids), cluster analysis, approximation algorithms for the Travelling Salesman Problem, and Euclidean geometry.
Key Formula
MST cost = sum of edge weights in tree T, where tree has (|V| - 1) edges
LaTeX: \text{MST cost} = \sum_{e \in T} w(e), \quad |E_T| = |V| - 1
| Symbol | Meaning | Unit |
|---|---|---|
| T | Set of edges in the minimum spanning tree | dimensionless |
| w(e) | Weight of edge e | cost units |
| |V| | Number of vertices in the graph | dimensionless |
| |E_T| | Number of edges in the spanning tree | dimensionless |
Worked Example
Problem
Find the MST of a graph with 4 vertices and edges: A-B=1, A-C=4, B-C=2, B-D=5, C-D=3. Use Kruskal's algorithm.
Solution
Step 1: Sort edges by weight: A-B=1, B-C=2, C-D=3, A-C=4, B-D=5. Step 2: Initialize each vertex as its own component: {A}, {B}, {C}, {D}. Step 3: Add A-B=1. Merges {A} and {B} → {A,B}. MST edges: {A-B}. Step 4: Add B-C=2. Merges {A,B} and {C} → {A,B,C}. MST edges: {A-B, B-C}. Step 5: Add C-D=3. Merges {A,B,C} and {D} → {A,B,C,D}. MST edges: {A-B, B-C, C-D}. Step 6: We have V-1=3 edges. Stop. Skip remaining edges (would form cycles).
Answer
MST = {A-B (1), B-C (2), C-D (3)}. Total MST cost = 1 + 2 + 3 = 6.
MST Algorithms: Kruskal's vs Prim's
| Property | Kruskal's | Prim's |
|---|---|---|
| Approach | Sort edges, add greedily | Grow tree from a vertex |
| Data Structure | Union-Find (Disjoint Set) | Priority Queue (min-heap) |
| Time Complexity | O(E log E) | O(E log V) with binary heap |
| Best for | Sparse graphs | Dense graphs |
| Handles disconnected? | Finds MSF (forest) | No — requires connected graph |
| Edge sorting needed? | Yes | No |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Greedy Algorithm
A Greedy Algorithm is an algorithmic paradigm that makes the locally optimal choice at each step with the hope of finding a globally optimal solution, without reconsidering previous choices. Greedy algorithms are efficient and simple, but they do not always produce the globally optimal solution — they work correctly only when the problem satisfies the greedy-choice property and optimal substructure. Classic examples include Kruskal's and Prim's algorithms for minimum spanning trees, Huffman coding, and activity selection.
Dijkstra's Algorithm
Dijkstra's Algorithm is a shortest-path algorithm that finds the minimum-cost path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) to greedily select the next closest unvisited vertex and relax its neighbors. It is foundational in network routing protocols (OSPF), GPS navigation, and map applications.
Topological Sort
Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u → v), vertex u appears before vertex v in the ordering. It is only possible for DAGs — graphs with cycles cannot be topologically sorted. Topological sort is essential in task scheduling, build systems (e.g., Makefile dependency resolution), course prerequisite ordering, and instruction scheduling in compilers.
"Spanning" comes from the English verb "to span" (Old English spannan, to stretch across), meaning connecting all vertices. "Minimum" is from Latin minimus (smallest). The concept was studied by Otakar Borůvka in 1926 for the Moravian electrical grid. Kruskal's algorithm was published by Joseph Kruskal in 1956, and Prim's algorithm by Robert Prim in 1957.