Greedy MST & Disjoint Set Union theory

A Greedy Algorithm is an algorithmic strategy that solves an optimization problem by making the locally optimal choice at each decision step, operating under the heuristic hope that a sequence of local optima will culminate in a globally optimal solution. Unlike Dynamic Programming, which systematically considers all subproblem alternatives and caches results, a greedy algorithm makes an irrevocable choice at each stage without ever backtracking or reconsidering prior decisions.



For a greedy algorithm to guarantee exact global optimality, the underlying problem must satisfy two fundamental conditions:

1. Optimal Substructure: An optimal solution to the overall problem contains within it optimal solutions to its subproblems.

2. The Greedy Choice Property: A globally optimal solution can be assembled by making locally optimal (greedy) choices without anticipating future subproblem configurations.



While these properties can often be proven ad hoc via cut-and-paste exchange arguments, Hassler Whitney established the unified mathematical foundation of greedy optimization in 1935 through Matroid Theory. A Matroid M is an algebraic combinatorial structure defined as an ordered pair M = (E, I), where E is a finite set of ground elements and I is a non-empty family of subsets of E (called independent sets) satisfying three formal axioms:

- Axiom 1 (Non-Emptiness): The empty set is independent: ∅ ∈ I.

- Axiom 2 (Hereditary Property): If set B ∈ I and A ⊆ B, then A ∈ I. Every subset of an independent set is independent.

- Axiom 3 (Exchange Property): If A, B ∈ I and |A| < |B|, then there exists an element e ∈ B \ A such that A ∪ {e} ∈ I.



In the context of graphs, the Graphic Matroid (or Cycle Matroid) M(G) = (E, I) defines E as the set of graph edges, and I as the family of all acyclic edge subsets (forests). It is straightforward to verify that forests satisfy all three axioms: subsets of forests are forests (Axiom 2), and if forest A has fewer edges than forest B, an edge from B can always be added to A without creating a cycle (Axiom 3).



The foundational Rado-Edmonds Theorem (Rado 1957, Edmonds 1971) proves the ultimate power of matroids: If weights are assigned to ground elements, a greedy algorithm (sorting elements by weight and iteratively adding the next lightest element that preserves independence) is guaranteed to find the minimum-weight maximal independent set if and only if the underlying structure is a Matroid! Because forests in a connected graph form a Graphic Matroid, Kruskal's greedy edge selection is mathematically guaranteed to construct the exact Minimum Spanning Tree.

The correctness of all greedy Minimum Spanning Tree algorithms rests upon two complementary combinatorial theorems governing edges across graph cuts and cycles: the Cut Property and the Cycle Property.



1. The Cut Property (Edge Inclusion Invariant):

Let G = (V, E) be a connected, undirected weighted graph. A Cut (S, V \ S) is a partition of the vertex set V into two non-empty, disjoint subsets S and V \ S. An edge e = (u, v) Crosses the cut if one endpoint resides in S (u ∈ S) and the other endpoint resides in V \ S (v ∈ V \ S).



The Cut Property states: For any cut (S, V \ S) of G, if edge e* is a crossing edge of strictly minimum weight, then e* must belong to every Minimum Spanning Tree of G. (If multiple crossing edges share the minimum weight, e* belongs to at least one MST).



Proof by Exchange Argument (Cut-and-Paste):

Suppose for contradiction that T is an MST of G that does not contain e*. Because T is a spanning tree, it connects all vertices; therefore, T must contain a simple path P connecting u and v. Because u ∈ S and v ∈ V \ S, the path P must cross the cut at least once, utilizing some crossing edge e' ≠ e*. Now, construct a new subgraph T' by removing e' and inserting e*:

T' = (T \ {e'}) ∪ {e*}

Removing e' disconnects T into two components (one in S, one in V \ S). Adding e* reconnects these two components, proving that T' is a valid spanning tree. The total weight of T' is:

w(T') = w(T) - w(e') + w(e*)

By the definition of e*, w(e*) ≤ w(e'). If w(e*) < w(e'), then w(T') < w(T), directly contradicting the assumption that T was a minimum spanning tree! If w(e*) = w(e'), then w(T') = w(T), proving that e* belongs to an alternative MST of identical minimum cost.



2. The Cycle Property (Edge Exclusion Invariant):

The Cycle Property states: For any simple cycle C in G, if edge e_max is an edge of strictly maximum weight on cycle C, then e_max cannot belong to any Minimum Spanning Tree of G.



Proof:

Suppose T is an MST that contains e_max. Removing e_max breaks cycle C and partitions T into two disconnected trees S and V \ S. Because C was a cycle, there must exist at least one other edge e' ∈ C crossing between S and V \ S. Adding e' reconnects the tree. Because e_max was the strictly heaviest edge on C, w(e') < w(e_max), yielding a tree with strictly smaller weight, a contradiction.



3. Algorithmic Manifestation:

- Prim's Algorithm directly enforces the Cut Property: at every step, it defines S as the set of vertices already in the growing tree, and greedily selects the lightest crossing edge connecting S to V \ S.

- Kruskal's Algorithm simultaneously enforces both properties: it considers edges in increasing weight order (Cut Property) and rejects any edge whose endpoints are already connected in the same component, thereby pruning edges that would become the heaviest edge on a cycle (Cycle Property).

Kruskal's Algorithm, published by Joseph Kruskal in 1956, is an edge-centric greedy algorithm that constructs a Minimum Spanning Tree by maintaining a growing forest of trees that gradually coalesce into a single spanning tree.



1. Algorithmic Mechanics:

- Step 1: Initialize each vertex v ∈ V as an isolated singleton tree component in a forest.

- Step 2: Sort all |E| edges in non-decreasing order of edge weights: w(e_1) ≤ w(e_2) ≤ ... ≤ w(e_|E|).

- Step 3: Iterate through the sorted edges sequentially. For each candidate edge e = (u, v):

- Test whether u and v belong to the same connected tree component.

- If they belong to different components, adding e connects two disjoint trees without forming a cycle. Accept e into the MST, and merge the two components into a single component.

- If they belong to the same component, adding e would create a cycle. Reject e and proceed to the next edge.

- Step 4: Terminate when exactly |V| - 1 edges have been accepted into the MST (or all edges have been inspected).



2. Complexity Analysis & The Sorting Bottleneck:

Let us analyze the computational cost of each stage:

- Sorting the Edges: Sorting |E| elements using comparison-based algorithms (such as Quicksort, Mergesort, or Introsort) requires Θ(|E| log |E|) comparisons. Because in any simple graph |E| < |V|², log |E| < 2 log |V| = Θ(log |V|). Therefore, sorting consumes Θ(|E| log |V|) time.

- Disjoint Set Operations: As the algorithm iterates through all |E| edges, it performs:

- Exactly 2 |E| Find operations (two Find calls per candidate edge to look up roots of endpoints u and v).

- At most |V| - 1 Union operations (one Union per accepted tree edge).

Using Disjoint Set Union with Path Compression and Union by Rank, m operations on n elements execute in O(m · α(n)) time. For 2|E| Find calls and |V| Union calls, the total DSU time is O(|E| · α(|V|)).



- Overall Running Time:

T(|V|, |E|) = O(|E| log |E| + |E| · α(|V|)) = O(|E| log |V|)



Because the inverse Ackermann function α(|V|) ≤ 4 for all conceivable universe scales, the DSU phase runs in virtually linear time O(|E|). Consequently, the comparison sorting step O(|E| log |E|) is the overwhelming computational bottleneck of Kruskal's algorithm! On sparse graphs where |E| = O(|V|), Kruskal runs in O(|V| log |V|) time. If edge weights are small integers permitting linear-time Radix Sort or Counting Sort in O(|E|) time, Kruskal's algorithm executes in nearly linear O(|E| · α(|V|)) time.

The Disjoint Set Union (DSU) data structure, also known as Union-Find, was developed by Bernard Galler and Michael Fisher in 1964 and rigorously analyzed by Robert Tarjan in 1975. DSU maintains a collection of disjoint dynamic sets S = {S_1, S_2, ..., S_k} over a universe of elements, supporting three fundamental operations:

- `MakeSet(x)`: Creates a new singleton set containing only element x.

- `Find(x)`: Returns the representative identifier (canonical root) of the set containing element x.

- `Union(x, y)`: Merges the set containing x with the set containing y into a single combined set.



1. Disjoint-Set Forest Representation:

DSU represents sets as directed trees, where each node maintains a single pointer to its parent: `parent[x]`. The root of a tree points to itself (`parent[root] == root`) and serves as the unique canonical representative of the entire set. In a naive implementation without optimizations, sequential unions can degenerate trees into linear chains of height h = n. In a linear chain, `Find(x)` must walk n pointers to reach the root, degrading operation latency to O(n) and making m operations consume quadratic Θ(m·n) time.



2. Optimization 1: Union by Rank (Balanced Merging):

To prevent tree degeneration, Union by Rank associates an integer attribute `rank[x]` with each root, representing an upper bound on the tree height (initially rank = 0 for singletons). When merging two sets with roots root_u and root_v:

- If rank[root_u] < rank[root_v], make root_v the parent of root_u (`parent[root_u] = root_v`). Rank of root_v remains unchanged.

- If rank[root_v] < rank[root_u], make root_u the parent of root_v (`parent[root_v] = root_u`).

- If rank[root_u] == rank[root_v], arbitrarily choose one (say root_u) as the parent, and increment its rank by 1: `rank[root_u]++`.

Union by Rank guarantees that a tree of rank r contains at least 2^r elements. Therefore, the maximum tree height is strictly bounded by h ≤ ⌊log₂ n⌋, ensuring that `Find` runs in worst-case O(log n) time.



3. Optimization 2: Path Compression (Dynamic Flattening):

Path Compression flattens the tree during every single `Find` call. When traversing from node x up to root r, the algorithm updates the parent pointer of every visited node along the path to point directly to root r:

```c

int find(int x) {

if (parent[x] != x)

parent[x] = find(parent[x]); // Recursive path compression

return parent[x];

}

```

While the first `Find(x)` walks depth h, all subsequent calls on any node along that path execute in instantaneous O(1) time!



4. Tarjan's Inverse Ackermann Bound O(α(n)):

When Path Compression and Union by Rank are combined, Tarjan (1975) proved that any arbitrary sequence of m DSU operations on n elements executes in worst-case O(m · α(n)) time, where α(n) is the extremely slow-growing inverse of the Ackermann function A(k, j).

The Ackermann function grows with mind-boggling rapidity: A(4, 2) is an exponential tower of 2s of height 65,536, a number vastly exceeding the number of atoms in the observable universe (~10⁸⁰). Consequently, for all practical input sizes n ≤ 10¹⁰⁰, α(n) ≤ 4. For all engineering purposes, each DSU operation executes in amortized constant time O(1).

Prim's Algorithm, independently developed by Vojtěch Jarník in 1930 and rediscovered by Robert Prim in 1957, is a vertex-centric greedy algorithm that grows a Minimum Spanning Tree continuously from an arbitrary seed vertex.



1. Algorithmic Mechanics:

- Step 1: Designate an arbitrary vertex s ∈ V as the starting tree root. Initialize the visited tree set S = {s}.

- Step 2: Maintain a priority queue Q containing all unvisited vertices v ∈ V \ S, where the priority key[v] represents the minimum weight of any edge connecting v to the active tree S. Set key[s] = 0 and key[v] = ∞ for all v ≠ s.

- Step 3: In each iteration, extract the vertex u with minimum key value from Q: `u = extract_min(Q)`. Add u to the tree set S, and add its parent edge (parent[u], u) to the MST.

- Step 4: For each unvisited neighbor v adjacent to u, inspect edge (u, v). If w(u, v) < key[v], update key[v] = w(u, v) and set parent[v] = u via `decrease_key(Q, v, w(u, v))`.

- Step 5: Repeat until all |V| vertices have been added to S, yielding exactly |V| - 1 MST edges.



2. Priority Queue Implementations & Asymptotic Complexity:

The time complexity of Prim's algorithm depends entirely on the priority queue data structure utilized:

- Unsorted Array: `extract_min` takes O(|V|) linear scan time; `decrease_key` takes O(1) time. Total time: |V| · O(|V|) + |E| · O(1) = O(|V|²). This is optimal for dense graphs where |E| = Θ(|V|²).

- Binary Min-Heap: `extract_min` takes O(log |V|) time; `decrease_key` takes O(log |V|) time. Total time: |V| · O(log |V|) + |E| · O(log |V|) = O((|V| + |E|) log |V|).

- Fibonacci Heap (Fredman and Tarjan 1987): `extract_min` takes O(log |V|) amortized time, but `decrease_key` executes in strictly O(1) amortized time! Total time: |V| · O(log |V|) + |E| · O(1) = O(|E| + |V| log |V|).



3. Algorithmic Comparison: Kruskal vs. Prim:

- Density Threshold: In sparse graphs where |E| ≈ O(|V|), Kruskal with DSU runs in O(|V| log |V|) and is simpler and faster in practice due to contiguous edge array cache locality. In dense graphs where |E| ≈ |V|², Kruskal requires sorting |V|² edges (taking O(|V|² log |V|) time), whereas Prim with a simple array runs in O(|V|²) time—significantly outperforming Kruskal!

- Implementation Simplicity: Kruskal operates directly on a flat edge list, requiring only an array sort and a parent array. Prim requires graph adjacency lists and priority queue pointer management.

Borůvka's Algorithm, invented by Czech mathematician Otakar Borůvka in 1926 to optimize the rural electrical electrification network of Moravia, was the very first Minimum Spanning Tree algorithm ever published. Unlike Kruskal's sequential edge-by-edge selection and Prim's single-component growth, Borůvka's algorithm operates via massive multi-component contraction rounds.



1. Algorithmic Mechanics:

- Step 1: Initialize the graph as a forest of |V| singleton components (each vertex is its own component).

- Step 2: In each round, every active component independently and simultaneously identifies its strictly minimum-weight crossing edge connecting it to another component.

- Step 3: All identified minimum crossing edges are simultaneously added to the MST, and connected components are contracted (merged) together.

- Step 4: Repeat rounds until only a single connected component remains.



2. Round Complexity Bound:

In each Borůvka round, every active component selects an incident edge. If there are k active components at the start of a round, at least k/2 distinct edges are selected, merging components in pairs. Therefore, each round cuts the number of active components by at least half: k_next ≤ k / 2.

Consequently, the total number of contraction rounds is strictly bounded by ⌈log₂ |V|⌉ rounds! In each round, scanning all incident edges takes O(|E|) time. The total sequential running time is:

T(|V|, |E|) = O(|E| log |V|)



3. Modern Parallel & Distributed Computing Advantage:

In modern computing, Borůvka's algorithm has experienced a massive resurgence in distributed and GPU-accelerated computing (Apache Spark GraphX, NVIDIA Gunrock):

- Kruskal's algorithm is fundamentally sequential: edges must be inspected one by one to avoid cycle race conditions in DSU.

- Prim's algorithm is fundamentally sequential: the tree expands one vertex at a time from the priority queue.

- Borůvka's algorithm is embarrassingly parallel! In Step 2, thousands of CPU cores or GPU threads can inspect components completely independently in parallel without locking. In distributed clusters, each machine scans its local partition, exchanges boundary edge minimums via message passing, and contracts components in parallel. Borůvka forms the foundational blueprint of modern exascale graph analytics.

Minimum Spanning Trees are not merely theoretical graph abstractions; they serve as critical infrastructure optimization engines across telecommunications, machine learning, and theoretical computer science.



1. Telecommunications and Physical Infrastructure Networks:

The original physical application of MSTs—pioneered by Borůvka for electrical grids and Bell Labs for telephone networks—remains pervasive today. When laying fiber optic internet cables, electrical transmission lines, or water pipelines between n cities, physical installation cost is proportional to edge length. Constructing an MST connects all n locations with guaranteed minimal total physical infrastructure cost. In computer networking, the Spanning Tree Protocol (STP / IEEE 802.1D) runs on Ethernet network switches to disable redundant bridge links and maintain an acyclic spanning tree, preventing broadcast radiation storms that would paralyze local area networks.



2. Single-Linkage Hierarchical Clustering (Machine Learning):

In unsupervised machine learning, clustering partitions n data points into k coherent clusters. Single-Linkage Hierarchical Clustering is mathematically isomorphic to Minimum Spanning Tree construction! Given a complete graph where edge weights w(u, v) represent Euclidean or cosine distance between data points, constructing the MST and deleting the k - 1 heaviest edges partitions the tree into exactly k disconnected components. Remarkably, this greedy deletion guarantees the Maximum Margin Clustering property: it maximizes the minimum separation distance between distinct clusters, forming the basis of phylogenetic evolutionary tree reconstruction in computational biology.



3. Approximation Algorithms for NP-Hard Problems (Metric TSP):

The Traveling Salesperson Problem (TSP)—finding the shortest Hamiltonian cycle visiting every vertex exactly once—is strongly NP-hard. However, when edge weights satisfy the Metric Triangular Inequality (w(u, v) ≤ w(u, w) + w(w, v)), Minimum Spanning Trees provide the mathematical backbone for constant-factor approximation algorithms:

- 2-Approximation Algorithm: An MST weight is a lower bound on the optimal TSP tour (deleting any edge from a TSP cycle yields a spanning tree, so w(MST) < w(TSP*)). Doubling the MST edges creates an Eulerian graph; shortcutting repeated vertices via triangular inequality produces a valid TSP tour of weight w ≤ 2 · w(MST) < 2 · w(TSP*).

- Christofides-Serdyukov 1.5-Approximation: Finds the odd-degree vertices in the MST, computes a Minimum-Weight Perfect Matching on them, and combines it with the MST. This achieves a tour within 1.5× of the global optimum—the benchmark polynomial approximation for metric TSP.