9. Minimum Spanning Trees

Definition: a subset of edges $T\subseteq E$ of a connected, weighted, undirected graph that:

1. Connects all vertices in V
2. Contains no cycles (it’s a tree)
3. Minimizes the total edge weight

Approach: Connect a node, and the nodes connected to it, to the rest of the nodes (i.e. any other node) using an edge with minimal weight (called a safe edge if unique and therefore included in all MSTs).

Prerequisite: Union Find

The graph above has the array $[1,1,1,1,4,4,4]$. Each node’s entry contains its ancestor.

How Find Works: Traverse the graph until you found a node that maps to itself.

How Union Works: Find the root node of both nodes. Replace the ancestor of one connected components with the ancestor of other connected component.

By Size (Rank): Always merge the connected component with less nodes (hight) into the larger one. Keep an array tracking size (height). When merging, set the size to their sum (or the height to $\max (h_{\text{smaller}}+1,h_{\text{larger}})$).

Path compression: Each time you traverse the graph to find the root node, remember all the nodes you pass through. Then connect them directly to the root node (possible by connecting them after performing a recursive call).

Note on the lectures: In the lectures, we saw the highly unusual approach having an array of ints, $\text{rep}$, and an array of lists, $\text{members}$. $\text{rep}$ contains the parent of each element. $\text{members}$ contains the children of each element. When we unionize $a$ and $b$, we check whether $a$ or $b$ has more members. Let’s say $a$ has more. We then change the parent of $b$ and of all the children of $b$ to $a$, unionize the list with $a$‘s, and delete its entries.

Runtime

Only find is relevant. Union is simply two finds + updating one root node and component size entry.

• Naive: $\mathcal{O}(V)$: you may have an extremely unbalanced tree if you always merge a tall tree into a single node.
• By size/rank: $\mathcal{O}(\log V)$
• By size/rank + path compression: $\mathcal{O}(\alpha (V))$ amortized, where $\alpha$ is the inverse Ackermann function (effectively $\mathcal{O}(1)$ for practical purposes)
  • Generally, all nodes are directly connected to the root (or via one node in between if two connected components just merged)

---

Boruvka

How it works: Always pick the edge with the lowest weight incident to every connected component, starting with the individual nodes. Use DFS to get the minimum edge of each connected component: save minimum edge found during DFS walk that doesn’t connect parts of component (using Union Find to check), reset it, and perform DFS walk from another unvisited node; add all the saved edges to the MST.

Does it really use DFS or does it go through all edges, keeping track of the cheapest on for each connected component?

Runtime

• $\mathcal{O}(\log V)$ iterations: In the worst case, you always connect pairs of connected components with each other.
• $\mathcal{O}(V+E)$ for performing DFS and parallel minimum finding. Union Find it negligable.

Total: $\mathcal{O}((V+E)\log V)$

Prim

How it works: Build up an MST from a single chosen node by iteratively adding the lowest edge going from the component to an unvisited node.

Runtime:

• $\mathcal{O}(V)$ iterations: every node must be added to the MST
• $\mathcal{O}(E\log E+V\log E)$ across all runs to insert $E$ edges into and extract $V$ edges from a priority queue of size $E$ $=\mathcal{O}((V+E)\log E)$ $=\mathcal{O}((V+E)\log V^2)$ $=\mathcal{O}(2\cdot (V+E)\log V)$ $=\mathcal{O}((V+E)\log V)$

Total: $\mathcal{O}((V+E)\log V)$

Kruskal

How it works:

• Sort edges by weight
• Take lowest edge
• Check if edge connects two already connected nodes using Union Find. If no, add edge to MST
• Repeat until there are no edges left

Runtime

• Sorting: $\mathcal{O}(E\log E)$ $=\mathcal{O}(E\log V^2)$ $=\mathcal{O}(2\cdot E\log V)$ $=\mathcal{O}(E\log V)$
• Adding edges + performing Union Find w/o path compression: $\mathcal{O}(E\log V)$

Total: $\mathcal{O}(E\log V)$