3. Minimum Spanning Trees

Spanning Trees

Spanning Tree

A spanning tree for a weighted graph $G=(V,E,w)$ is a tree $T=(V,E^{\prime })$ in which each vertex is connected and $E^{\prime }\subseteq E$. It is any sub-graph of $G$ that connects all nodes without any cycles.

Link to original

Minimum Spanning Tree

For all spanning trees, there must be one where the sum of all weights is minimal, this is called a minimum spanning tree (MST). In this example, $\sum \text{weights}=37$.

Link to original

Kruskal’s Spanning Tree Algorithm

Kruskal's Spanning Tree Algorithm

$\text{KRUSKAL-MST}(G)$:

1. Sort the edge list $E$ by weight (shortest first)
2. Initialise a set $T=\varnothing$
3. While sorted list $E$ is not empty:
   1. Dequeue the shortest edge $(u,v)$ from $E$
   2. If $T\cup \{(u,v)\}$ is acyclic:
      1. Update $T\leftarrow T\cup \{u,v\}$
4. Return tree $T$

Link to original

Theorem: Termination time for Kruskal’s is $O(|E|\log |E|)$.

1. For step 1, we need to sort $E$ which can be done using merge-sort or some equivalently efficient sorting algorithm. Time to sort $E$ by weight $=O(|E|\log |E|)$.
2. Steps 3.1 and 3.2.1 are primitive and take $O(1)$ steps for each iteration $(u,v)\in E$. The total time for these is $\sum (O(1)+O(1))=O(|E|)$
3. Step 3.2 requires checking whether $u$ and $v$ are already connected since a second connection would create a cycle. Here, we use an algorithm called quick-union find. Total time to check $=O((|V|+|E|)\alpha (|V|))$, where $\alpha$ is a very slow growing function. (see Cormen et al. 21.3)
4. Hence the total worst-case termination time is: $$\begin{array}{rl}T(V,E)& =O(|E|\log |E|)+O(|E|)+O((|V|+|E|)\alpha (|V|))\\ & =O(|E|\log |E|)\text{ dominates all terms}\end{array}$$

## Prim's Spanning Tree Algorithm ![[Prim's Spanning Tree Algorithm]] ### Theorem: Termination time for Prim's is $O(|E| + |V| \log |V|)$. - It is subject to the data structure used for maintaining the priority queue, though we can use a structure called a **Fibonacci Heap** to obtain these complexity bounds. (*see Cormen et al. 19*)