26 Minimum Spanning Trees via Kruskal's algorithm

Algorithm: Finding a MST $T=(V,E^{\prime })$ of $G=(V,E)$ with edge-costs given by $\mathrm{cost}:E\to {\mathbb{R}}^{+}$

$$\begin{array}{rl}1:& \text{Order the edges of }E\text{ as }{e}_1,e_2,\dots ,e_m\text{ in increasing order of costs}\\ 2:& \text{Initialize }{E}^{\prime }=\varnothing \text{ and }i=1\\ 3:& \text{while }i\le m\text{ do}\\ 4:& \text{if adding }{e}_i\text{ to }{E}^{\prime }\text{ does not create a cycle then}\\ 5:& \text{Add }{e}_i\text{ to }{E}^{\prime }\\ 6:& \text{else}\\ 7:& \text{Do not add }{e}_i\text{ to }{E}^{\prime }\\ 8:& \text{end if}\\ 9:& \text{Increase }i\text{ by }1\\ 10:& \text{end while}\end{array}$$

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

• while loop runs $m$ times
• Inside each while loop we need to check of adding current edge creates a cycle $O(n)$ time

Correctness of Kruskal’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 Kruskal’s algorithm adds the edge $v-w$ at this step.
• Let $S$ be set of all vertices to which $v$ had a path before this step.
• Clearly $w\notin S$
• Before this step, by definition of $S$, no edges from $S$ to $V\setminus S$ have been added
• Since $v\in S$ and $w\notin S$ and Kruskal’s algorithm adds edges in increasing order of costs, it follows that $v-w$ is the cheapest edge with one end-point in $S$ and other end-point in $V\setminus S$.