Minimum Spanning Tree

Overview

Let $G=⟨V,E⟩$ be a connected, undirected graph. Let $w(u,v)$ denote the weight of each edge $\{u,v\}\in E$.

A spanning tree $T$ is an acyclic subset $T\subseteq E$ that connects all the vertices of $G$. A minimum spanning tree is a spanning tree with $w(T)$, defined as follows, minimized:

Kruskal's Algorithm

Let $G=⟨V,E⟩$ be an undirected graph and $w:E\to \mathbb{R}$ be a weight function. Kruskal's algorithm is a greedy algorithm for finding an MST in $G$. Assuming $G$ is represented as an adjacency-list:

1. Set $A=\varnothing$.
2. For each vertex $v\in V$, make a disjoint-set $\{v\}$.
3. Create a sorted list of the edges in $E$ in increasing order.
4. For each edge $\{u,v\}$ in the sorted list, check if the sets containing $u$ and $v$ are disjoint. If so, join the disjoint sets and set $A=A\cup \{\{u,v\}\}$.

Upon termination, $A$ is the desired MST.

Prim's Algorithm

Let $G=⟨V,E⟩$ be an undirected graph and $w:E\to \mathbb{R}$ be a weight function. Prim's algorithm is a greedy algorithm for finding an MST in $G$. Assume $G$ is represented as an adjacency-list. Given an empty min priority queue $Q$ and an arbitrary vertex $s\in V$:

1. For each $v\in V$, set $v.\text{key}=\mathrm{\infty }$ and $v.\pi =\text{NIL}$.
2. Set $r.\text{key}=0$.
3. Insert all vertices into $Q$.
4. While $Q\ne \varnothing$:
5. Let $m$ be the extracted minimum of $Q$.
6. For each vertex $v\in Q$ adjacent to $u$ such that $w(u,v)<v.\text{key}$:
   1. Set $v.\pi =u$ and $v.\text{key}=w(u,v)$.
   2. Decrease the key of $v$ in $Q$.

Upon termination, $\{⟨v,v.\pi ⟩\mid v\in V-\{r\}\}$ is the desired MST.