# Minimum Spanning Tree

• Let $G = (V, E)$ be an undirected graph.

A spanning tree $T = (V, F)$ of $G$ is a graph containing the same vertices as $G$, and $|V| - 1$ edges (called $F$) of $G$ that form a tree. (There there is exactly one path between any two vertices of $T$.)

If $G$ is not connected, it has no spanning tree, but we can instead compute a spanning forest, or collection of spanning trees, having one tree for each connected component of $G$.

• If $G$ is weighted, then a minimum spanning tree $T$ of $G$ is a spanning tree of $G$ whose total weight (summed over all edges of $T$) is minimal. In other words, no other spanning tree of $G$ has a smaller total weight.

### Kruskal’s Algorithm

• Kruskal’s algorithm computes the minimum spanning tree of $G$ as follows:

• Create a new graph $T$ with the same vertices as $G$, but no edges (yet).

• Make a list of all the edges in $G$.

• Sort the edges by weight, from least to greatest.

• Iterate through the edges in sorted order.

For each edge $(v, w)$: if $v$ and $w$ are not connected by a path in T, add $(v, w)$ to $T$.

• Since Kruskal’s algorithm never adds $(v, w)$ if some other path already connects $v$ and $w$, $T$ is guaranteed to be a tree (if $G$ is connected) or a forest (if $G$ is not).

• Sorting the edges takes $O(|E| \log |E|)$ time. To determining whether two edges are already connected by a path, we can use disjoint sets, so that all the iterations of the look take less than $O(|E| \log |E|)$ time.

• The running time of Kruskal’s algorithm is $O(|V| + |E| \log |E|)$ on adjacency lists and $O(|V|^2 + |E| \log |E|)$ on adjacency matrix (it takes $\Theta(|V|^2)$ time to make a list of all the edges).

Since we use adjacency lists when $|E| < |V|^2$, $\log |E| < 2 \log |V|$, so we can also say that the running time of Kruskal’s algorithm for adjacency lists is $O(|V| + |E| \log |V|)$.

• Visualization:

### Prim’s Algorithm

• Prim’s algorithm computes the minimum spanning tree of $G$ as follows:

• For all $v$ in $V$, set $v.distance = \inf$, $v.parent = nil$.

• Create a new graph $T$ with the same vertices as $G$, but no edges (yet).

• Choose a vertex $s$ from $V$. Set $s.distance = 0$.

• Make a priority queue $Q$ of all the vertices, with distance as the priority.

• While $Q$ is not empty:

• $v = Q.removeMin$

• Add the edge $(v, v.parent)$ to $T$.

• For each vertex $w$ such that $e = (v,w) \in E$ and $w \in Q$:

if $e.weight < w.distance$, set $w.distance = e.weight$ and $w.parent = v$.

• We begin with a single root vertex $r$, and add edges connecting new vertices until they are all connected. We’ll use a “distance” variable for each vertex to keep track of the shortest edge so far for joining that vertex to the result tree T. We’ll also track which edge that is.

• The total time for $|V|$ removeMin operations will be in $O(|V| \log |V|)$. The total time for $|E|$ updatePriority operations will be in $O(|E| \log |V |)$. So the total running time is in $O((|V| + |E|) \log |V|)$, which is $O(|E| \log |V|)$.

• Visualization: