MIT 6.1220 — Lecture 8

Minimum Spanning Trees

Definition (Tree). A tree is a connected acyclic graph.

Definition (Spanning Tree). A spanning tree of a graph $G = (V, E)$ is a tree $T = (V, F)$ with $F \subseteq E$ .

Claim. Every connected graph has a spanning tree.

Proof: There are many proofs (induction, BFS, …). Here's an algorithmic proof:

Algorithm. Initialize $F \leftarrow E$ . While $F$ contains a cycle $C$ , repeatedly pick edges from $C$ at random to remove from $F$ . Return $F$ when done.

This terminates and yields a connected, acyclic graph (i.e. a spanning tree), done. Here's another proof:

Algorithm. Initialize $F \leftarrow \emptyset$ . While $(V, F)$ is not connected, repeatedly draw edges between connected components of $(V, F)$ . Return $F$ when done.

This terminates and yields a connected, acyclic graph (i.e. a spanning tree), done.

Problem. (Minimum Spanning Tree) Find the spanning tree of a weighted graph with least total edge weight.

Here's a useful fact for building spanning tree intuition, from the cycle perspective.

Claim. Say $T = (V, F)$ is a spanning tree of $G = (V, E)$ , and consider any edge $e = \overline{uv} \in E \setminus F$ . Then:

There is a unique path $P_e \subseteq F$ connecting $u$ and $v$ in $T$ .
There is a fundamental cycle of $e$ with respect to $T$ defined by $P_e \cup \{e\}$ .
For all $e' \in P_e$ , the subgraph $T' := (V, F \setminus \{e'\} \cup \{e\})$ is also a spanning tree.

Note that the first two bullet points don't really require $e \in E$ , or care about $G$ at all, really.

And here's a similar fact, from the cutting perspective.

Claim. Say $T = (V, F)$ is a spanning tree of $G = (V, E)$ , and consider any edge $e = \overline{uv} \in F$ . Then:

If we remove $e$ from $T$ , we get two connected components $A$ and $B$ (containing $u$ and $v$ , respectively).
For any $e' \in E$ connecting $A$ and $B$ , the subgraph $T' := T \setminus \{ e \} \cup \{e'\}$ is a spanning tree.

This inspires Kruskal's Algorithm, which constructs $T$ by adding edges to a forest.

Solution. (Kruskal's Algorithm) Here's the algorithm, in full.

Initialize $F \leftarrow \emptyset$ . Initialize a $\textsc{Union-Find}$ data structure to store connected components. Sort $E$ by weight.
Scan through all edges $e_i = (u_i, v_i)$ for all $i = 1, 2, \dots, |E|$ , in increasing order of weight.
- For each $(u_i, v_i)$ such that $\textsc{Find-Set}(u_i) \neq \textsc{Find-Set}(v_i)$ , add $e_i$ to $F$ and apply $\textsc{Union}(u_i, v_i)$ .
Finally, return $F$ .

Proof: It suffices to demonstrate by induction that $F$ is always a subset of some MST.

Suppose $F \subseteq T$ initially, for some MST $T$ . Now we draw an edge $e = (u_i, v_i)$ between the connected component $A$ of $u_i$ in $(V, F)$ and $B := V \setminus A$ . (Intuitively, we should think of edge $e$ as bridging across the “cut” $V = A \sqcup B$ .)

If $e = (u_i, v_i) \in T$ , we're fine. Otherwise, take the fundamental cycle of $e$ with respect to $T$ ; this cycle must bridge across the “cut” $V = A \sqcup B$ a second time along some edge $e'$ .

You can now check that $T' := T \setminus \{e'\} \cup \{e\}$ is also an MST, so $F \cup \{e\}$ remains a subset of an MST $T'$ . $\blacksquare$

Here's our runtime analysis of Kruskal's Algorithm.

Solution. (Kruskal's Algorithm Runtime) There's only three major steps.

Initializing the $\textsc{Union-Find}$ data structure takes $O(|V|)$ time.
Sorting $E$ takes $O(|E| \log |E|) = O(|E| \log |V|)$ time (since $|E| = O(|V|^2)$ ).
All of the $\textsc{Union-Find}$ operations take $O(|E| \cdot \alpha(|V|))$ time.

So in total, we can say the runtime of Kruskal's Algorithm is $O(|E| \log |V|)$ .

This also inspires Prim's Algorithm, which grows $F$ by connecting vertices to a tree.

Remark. Recall the following properties of a priority queue implemented by a Fibonacci heap.

A priority queue $Q$ stores keys together with their values.
The method $Q.\textsc{DeleteMin}()$ returns the lowest-value key of $Q$ and deletes it in $O(\log n)$ amortized time.
The methods $Q.\textsc{Insert}(k, v)$ and $Q.\textsc{DecreaseKey}(k, v)$ run in $O(1)$ amortized time.

Solution. (Prim's Algorithm) Here's the algorithm, in full:

Initialize $F = (V_F, E_F) \leftarrow (\emptyset, \emptyset)$ .
Initialize a $\textsc{Priority Queue}$ $Q$ and an array $\textsc{Parent}[u]$ .
- The queue $Q$ will store keys $v \in V$ with values $d(v) := \min \{ w(u, v) \mid u \in V_F \text{ and } \overline{uv} \in E\}$ .
- The $\textsc{Parent}$ array will store for each $v$ the vertex with $w(v, \textsc{Parent}[v]) = d(v)$ .
- Initialize $\textsc{Parent}[u] \leftarrow \textsc{Null}$ for all $u \in V$ .
Pick some starting vertex $s$ , and initialize $Q.\textsc{Insert}(s, 0)$ and $Q.\textsc{Insert}(v, \infty)$ for all $v \neq s$ .
While $Q$ is nonempty…
1. Add the edge $(u, \textsc{Parent}[u])$ to $F$ , where $u \leftarrow Q.\textsc{DeleteMin}()$ .
  
  (Add nothing when $\textsc{Parent}[u] = \textsc{Null}$ , as on the first iteration.)
2. Now that we've added $u$ to $F$ , we need to make some updates. For each $v$ neighboring $u$ still in $Q$ …
  - Update $d(v) \leftarrow \min\{d(v), w(u, v)\}$ , and update $Q.\textsc{DecreaseKey}(v, d(v))$ as needed.
  - If $d(v)$ was updated, then also update $\textsc{Parent}[v] \leftarrow u$ .
Return $F$ when done.

Proof: Again, we wish to show $F$ is invariably a subset of some MST.

It's actually the same argument as before. Consider the cut $V = V_F \sqcup (V \setminus V_F)$ . You can do whatever to bridge this cut and the result will still be an ST, minimal if you do the “whatever” with minimal weight. $\blacksquare$

This runs in $O(|E| + |V|\log |V|)$ time, since…

We have $|V|$ iterations of $Q.\textsc{DeleteMin}()$ , each of which takes $O(\log |V|)$ time.
The updates $d(v) \leftarrow \min \{d(v), w(u, v)\}$ have amortized $O(1)$ cost with a Fibonacci heap, $O(|E|)$ total.