The Two Fundamental MST Optimality Laws
Robert Tarjan termed these the Blue Rule (Cut Property) and Red Rule (Cycle Property): applying them in any order colors exactly $|V| - 1$ edges Blue (in the MST).
- Cut Property (Inclusion): Let $S \subset V$ ($\emptyset \neq S \neq V$) be any cut of $G$, and let $e = (u, v)$ with $u \in S, v \in V \setminus S$ be a strictly minimum-weight edge crossing the cut $(S, V \setminus S)$. Then $e$ belongs to every MST of $G$ (if ties exist, $e$ belongs to some MST).
Exchange Proof: Suppose an MST $T$ omits $e$. Adding $e$ to $T$ creates a unique fundamental cycle $C$ that must cross the cut $(S, V \setminus S)$ at least one other time via some edge $e' \in T$ with $w(e') \ge w(e)$. Replacing $e'$ with $e$ yields a spanning tree $T' = T \setminus \{e'\} \cup \{e\}$ with $w(T') = w(T) + w(e) - w(e') \le w(T)$. - Cycle Property (Exclusion): Let $C$ be any simple cycle in $G$, and let $e_{\max} \in C$ be a strictly maximum-weight edge on $C$. Then $e_{\max}$ cannot belong to any MST of $G$.
- Minimax Path Corollary: For any two vertices $x, y \in V$, the unique path between $x$ and $y$ inside an MST $T$ minimizes the maximum edge weight $\max_{e \in P} w(e)$ over all paths $P$ in $G$.
Comparing Kruskal's, Prim's, and Borůvka's Algorithms
- Kruskal's Algorithm ($O(E \log E)$): Sorts all edges by weight and adds $e = (u, v)$ if $\text{dsu.unite}(u, v)$ succeeds. When $e$ connects components $C_u$ and $C_v$, $e$ is the lightest edge crossing the cut $(C_u, V \setminus C_u)$. Ideal for sparse graphs where edges are already in a flat buffer.
- Prim's Algorithm ($O(E \log V)$ or $O(V^2)$): Grows a single component $S$ starting from root $0$, repeatedly extracting the lightest edge crossing $(S, V \setminus S)$. On dense graphs ($E \approx V^2$), an array-based Prim without a heap runs in optimal $O(V^2)$ time (beating $O(V^2 \log V)$ binary heaps!).
- Borůvka's Algorithm ($O(E \log V)$ in $\le \lceil \log_2 V \rceil$ rounds): In each round, every current component simultaneously selects its cheapest outgoing edge and merges. Because every active component merges with at least one neighbor, the number of components at least halves each round ($\le \log_2 V$ rounds). Essential for parallel/GPU MST and implicit graphs (e.g., finding the MST where $w(u, v) = a_u \oplus a_v$ using a binary Trie).
Trace Kruskal’s weight-sorted edge scan alongside DSU component merging: accept every light edge crossing a cut (find(u) != find(v)) and reject any cycle-closing heaviest edge (find(u) == find(v)).
Invariant & State
Although Prim's $O(E \log V)$ looks asymptotically equivalent to Kruskal's $O(E \log E)$, Kruskal spends $90\%$ of its runtime inside std::sort (Introsort / PDQSort) over a contiguous array of 12-byte {w, u, v} structs—maximizing L1 cache hits and SIMD-friendly comparisons—followed by a sequential scan with $O(1)$-cached DSU lookups, terminating early as soon as $V - 1$ edges are added.
Complexity Matrix
| Algorithm | Time Complexity | Auxiliary Space | Optimal Regime |
|---|---|---|---|
| Kruskal's (Sort + DSU) | O(E log E) | O(V) | Sparse graphs ($E = O(V)$), edge lists |
| Prim's (Binary Heap) | O(E log V) | O(V) | Adjacency list graphs |
| Prim's (Flat Array, No Heap) | O(V²) | O(V) | Dense / geometric graphs ($E = \Theta(V^2)$) |
| Borůvka's Algorithm | O(E log V) | O(V) | Parallel / GPU & implicit/XOR edge weights |
Production Implementation: Kruskal's MST & Dense $O(V^2)$ Prim's MST
#include <vector>
#include <algorithm>
#include <limits>
struct WeightedEdge {
int u, v;
long long weight;
bool operator<(const WeightedEdge& other) const noexcept {
return weight < other.weight;
}
};
// Returns (totalMSTWeight, selectedEdges). If disconnected, selectedEdges.size() < n - 1.
std::pair<long long, std::vector<WeightedEdge>> kruskalMST(int n, std::vector<WeightedEdge> edges) {
std::sort(edges.begin(), edges.end());
std::vector<int> p(n, -1);
auto find = [&](int x) {
int r = x;
while (p[r] >= 0) r = p[r];
while (x != r) { int nxt = p[x]; p[x] = r; x = nxt; }
return r;
};
long long totalWeight = 0;
std::vector<WeightedEdge> mst;
mst.reserve(n > 0 ? n - 1 : 0);
for (const auto& e : edges) {
int ru = find(e.u), rv = find(e.v);
if (ru != rv) {
if (p[ru] > p[rv]) std::swap(ru, rv);
p[ru] += p[rv];
p[rv] = ru;
totalWeight += e.weight;
mst.push_back(e);
if (static_cast<int>(mst.size()) == n - 1) break;
}
}
return {totalWeight, mst};
}If a graph has duplicate edge weights (e.g., a triangle $A-B-C$ where all three edges have weight $5$), and in a Borůvka round component $A$ picks $(A, B)$, $B$ picks $(B, C)$, and $C$ picks $(C, A)$, adding all three simultaneously creates a cycle! Always break weight ties deterministically using the lexicographical tuple (weight, min(u, v), max(u, v)) so all edge weights become strictly distinct.