Minimum Spanning Trees

Purpose

The Minimum Spanning Tree (MST) problem focuses on isolating an optimized subset of edges that completely links every vertex across a connected, weighted undirected graph without introducing structural cycles, while minimizing the absolute sum of all chosen edge weights. This serves as the computational foundation for low-cost distribution networks (e.g., minimizing physical cable layouts across a system layout).

Category: Graph Optimization / Network Management
Solves: Total cost minimization across distribution systems.
Typical use cases: Designing high-efficiency utility routing, clustering analysis, network backbone layout design.

---

Concepts

Defining the Spanning Tree

For any connected, undirected graph $G=(V,E)$, an internal Spanning Tree is a specific subgraph $G^{\prime }=(V,E^{\prime })$ that spans every single vertex of $V$, preserves baseline connectivity, introduces absolutely zero cycles, and maintains exactly $|V|-1$ total edges.

Uniqueness Invariant

If every single edge weight metric across a connected graph structure is distinct and unique, the graph contains exactly one absolute Minimum Spanning Tree solution.

The Cut Property

The foundational mathematical theorem used to prove the global correctness of greedy graph optimization models. For any valid cut that partitions a graph’s vertices into two isolated tracking subsets, the single lowest-cost edge crossing that cut boundary is mathematically guaranteed to be included in an optimal Minimum Spanning Tree.

---

How It Works

While standard weight-blind traversal engines like BFS can discover generic spanning structures in $O(|V|+|E|)$ time, they are weight-blind. They accept the first paths they encounter, missing optimal weight choices. To handle weighted layouts safely, we deploy specialized greedy optimization routines.

Key Idea

Prim’s grows a single unified tree entity out from a singular root node, while Kruskal’s aggregates individual structural components across an open grid ecosystem using an underlying disjoint set lookup to bridge isolated forests.

---

Algorithm Implementations

Prim’s Algorithm (Vertex-Centric Approach)

Prim’s grows a unified spanning structure node-by-node, starting from an arbitrary root vertex. This design mirrors Dijkstra’s Algorithm by maintaining a priority queue tracking the minimum cost to attach unvisited nodes to the growing tree.

Algorithm 50 Prim's MST Algorithm

procedure Prim($G, startVertex$)

for all $v \in \text{Vertices}(G)$ do

$\text{key}[v] \gets \infty$

$\text{parent}[v] \gets \text{NULL}$

$\text{visited}[v] \gets \text{FALSE}$

$\text{key}[startVertex] \gets 0$

$\text{Queue} \gets \text{InitializeMinPriorityQueue()}$

Insert($\text{Queue}, \text{startVertex}, 0$)

while $\text{Queue is not empty}$ do

$u \gets$ ExtractMin($\text{Queue}$)

$\text{visited}[u] \gets \text{TRUE}$

for all $(u, v) \in \text{AdjacentEdges}(G, u)$ do

if $\text{visited}[v] == \text{FALSE} \land \text{Weight}(u, v) < \text{key}[v]$ then

$\text{parent}[v] \gets u$

$\text{key}[v] \gets \text{Weight}(u, v)$

DecreaseKeyOrInsert($\text{Queue}, v, \text{key}[v]$)

Kruskal’s Algorithm (Edge-Centric Approach)

Kruskal’s shifts focus to the graph edges. It handles components as a decentralized collection of small trees, repeatedly pulling the global absolute lowest-cost edge available out of a queue and merging components if they pass validation checks via a disjoint-set manager.

Algorithm 51 Kruskal's MST Algorithm

procedure Kruskal($G$)

$MST \gets \emptyset$

for all $v \in \text{Vertices}(G)$ do

Makeset($v$)

$\text{Queue} \gets \text{InitializeMinPriorityQueue()}$

for all $e \in \text{Edges}(G)$ do

Insert($\text{Queue}, e, \text{Weight}(e)$)

while $\text{Queue is not empty} \land$ Size(MST) < Count($\text{Vertices}(G)$) - $1$ do

$e \gets$ ExtractMin($\text{Queue}$)

$rootU \gets$ Find($e.u$)

$rootV \gets$ Find($e.v$)

if $rootU \neq rootV$ then

$MST \gets MST \cup \{e\}$

Union($rootU, rootV$)

return $MST$

---

Comparison of Optimization Approaches

Performance Parameter	Prim’s Algorithm Strategy	Kruskal’s Algorithm Strategy
Core Architecture	Concentric Vertex Expansion	Distributed Edge Consolidation
Priority Queue Contents	Bounded Vertices ($O(\Vert V\Vert )$)	Total Graph Edges ($O(\Vert E\Vert )$)
Cycle Prevention Mechanism	Simple visited[] Boolean Check	Union-Find Up-Trees
Ideal Performance Target	Dense Graph Topologies	Sparse Graph Topologies
Negative Weights Handling	Supported natively	Supported natively
Asymptotic Complexity	$O(\Vert E\Vert \log \Vert V\Vert )$ using Binary Heap	$O(\Vert E\Vert \log \Vert E\Vert )$ driven by initial sort

---

Related Notes

• Disjoint Sets & Up-Trees — Direct component partition manager running Kruskal’s cycle verification routines.
• Graph Representations — Dictates neighbor discovery speeds ($O(|V|)$ vs $O(\text{deg}(u))$), directly scaling Prim’s inner loop.