25 Minimum Spanning Trees via Prim's Algorithm

Minimum Spanning Tree (MST) problem

Given an undirected, connected graph $G=(V,E)$ with edge-costs given by $\mathrm{cost}:E\to {\mathbb{R}}^{+}$, find a spanning tree $T=(V,E^{\prime })$ such that ${\sum }_{e\in E^{\prime }}\mathrm{cost}(e)$ is minimised

Prim’s algorithm

$$\begin{array}{r}\text{Algorithm : }\text{Finding a MST }T=(V,E^{\prime })\text{ of }G=(V,E)\text{ with edge-costs given by }\mathrm{cost}:E\to {\mathbb{R}}^{+}\end{array}$$ $$\begin{array}{rl}1:& \text{Let }S\text{ be set of explored vertices}\\ 2:& \text{Initialize }S=\{s\}\text{ where }s\text{ is any vertex}\\ 3:& \text{Initialize }{E}^{\prime }=\varnothing \\ 4:& \text{while }S\ne V\text{ do}\\ 5:& \text{Select a vertex }v\notin S\text{ which minimizes }\underset{e=u-v,u\in S}{\min }\mathrm{cost}(e)\\ 6:& \text{Add }v\text{ to }S\text{ and }e\text{ to }{E}^{\prime }\\ 7:& \text{end while}\end{array}$$

Running time is $O(mn)$ where $n,m$ is number of vertices, edges respectively

• while loop runs $(n-1)$ time from $|s|=1$ to $|s|=n$
• $\forall$ explored set $S$, number of edges between explored and non-explored is $\le |E|=m$

Correctness of Prim’s algorithm

Assumption : All edge costs are distinct

Theorem

For any $S\subset V$, let $e$ be the edge of minimum cost having one end-point in $S$ and other end-point in $VS$. Then, every MST contains the edge $e$

• Suppose there is a MST $T$ which does not contain this edge $e$ whose endpoints are $v\in S$ and $w\notin S$
• We will (carefully) find an edge $e^{\prime }$ in $T$ such that $\mathrm{cost}(e^{\prime })>\mathrm{cost}(e)$
• And replacing $e^{\prime }$ with $e$ gives a spanning tree of smaller cost. Contradiction