Minimum Spanning Tree (Kruskal)
Why it exists
Problem: When connecting physical infrastructure (like power grids or network cables), you need total connectivity for the absolute minimum total cost, without creating redundant loops.
Better idea: Sort all possible connections by cost, and greedily pick the cheapest ones as long as they don't form a cycle. This relies on the graph cut property to guarantee a globally minimal spanning tree.
Mental model
Imagine building a network using the cheapest available cables first. If a cable connects two cities already linked (creating a cycle), you discard it and check the next cheapest.
Kruskal's algorithm abandons vertex-based traversal and focuses on edges. It starts by sorting all edges in ascending order of weight. It then evaluates each edge exactly once. To efficiently verify whether adding an edge creates a cycle, it delegates the check to a Union-Find data structure. The process stops when the tree spans all vertices (V-1 edges).
Repeated decision: At each step: is the next-cheapest edge safe to take, i.e. does it connect two different components?
Explanation
A Minimum Spanning Tree (MST) is the cheapest set of edges that connects all `V` nodes with no cycles, strictly requiring `V-1` edges. MSTs are defined specifically for **undirected**, weighted graphs.
### The Algorithm
1. **Sort**: Place all edges in a list and sort them by weight in ascending order.
2. **Initialize**: Create a Union-Find data structure where each node is its own component.
3. **Greedy Choice**: Iterate through the sorted edges. For each edge `(u, v)` with weight `w`:
- Check if `Find(u) == Find(v)`.
- If they match, `u` and `v` are already connected; adding this edge would close a cycle. Skip it.
- If they differ, this edge connects two separate components. Add it to the MST, and `Union(u, v)`.
4. Stop when you've accepted exactly `V-1` edges.
### Complexity
The dominant cost is the initial sorting of edges, which takes `O(E log E)`. The subsequent Union-Find operations take effectively constant time, making the overall complexity `O(E log E)`. (Note: Prim's algorithm is an alternative, but Kruskal's is extremely elegant once Union-Find is available). This is our first major bridge into Greedy algorithms: making the locally cheapest choice unconditionally leads to the globally best MST.
### Hand-Trace
Consider an undirected graph with 4 nodes (A, B, C, D) and 5 edges:
`A-B (weight 1)`, `B-C (weight 2)`, `A-C (weight 3)`, `C-D (weight 4)`, `B-D (weight 5)`.
1. Sort edges: `(A,B,1)`, `(B,C,2)`, `(A,C,3)`, `(C,D,4)`, `(B,D,5)`.
2. Evaluate `(A,B,1)`: Different components. Take it. MST has `[(A,B)]`.
3. Evaluate `(B,C,2)`: Different components. Take it. MST has `[(A,B), (B,C)]`.
4. Evaluate `(A,C,3)`: `Find(A) == Find(C)` because they are connected via B. Skip it.
5. Evaluate `(C,D,4)`: Different components. Take it. MST has `[(A,B), (B,C), (C,D)]`.
6. We have `4 - 1 = 3` edges. The MST is complete with total weight `1 + 2 + 4 = 7`.
Common mistakes
- Detecting cycles with DFS/BFS: Running a full graph traversal to check for cycles before adding each edge turns an efficient algorithm into an O(E * (V+E)) nightmare. Always use Union-Find.
- Stopping too late: Iterating over every single edge even after finding V-1 valid edges wastes time. The MST is strictly complete at V-1 edges.
Recall questions
- What defines a Minimum Spanning Tree?
- What data structure does Kruskal's algorithm rely on to prevent cycles?
- What dictates the time complexity of Kruskal's algorithm?
Questions & answers
How would you modify Kruskal's to find the Maximum Spanning Tree?
Sort the edges in descending order of weight, then apply the exact same Union-Find logic.
Approach: Recognize that the greedy choice works for both minimizing and maximizing as long as the sorting order flips.
You have a graph where some edges are already built. How do you find the cheapest way to connect the rest?
Add all pre-built edges to the Union-Find first (ignoring their weights), then run Kruskal's normally on the remaining edges.
Approach: Initialize the DSU state with the existing infrastructure to effectively cost them at 0.
Continue learning
Previous: Weighted vs unweighted
Previous: Union-Find