Finding the minimum spanning tree

Prim’s algorithm

The cut property naturally extends to an algorithm for finding the MST.

1. Initialize cut $S=\{v\}$ for any arbitrary $v\in V$ and the tree $T=\varnothing$ to begin with.
2. Find the min-weight edge $e$ such that $e=(v,u)$ and it crosses $(S,V-S)$ over all the vertices in $S$.
3. Update $S\leftarrow S\cup \{u\}$, and add $e$ to $T$.
4. When the cut $S$ includes all the vertices in the graph $(V=S)$, return $T$ as the MST for $G$.

Finding the min-weight edge

This is not a trivial task and we need to use a min-heap in order to minimize the time we take to find the min-weight edge in $S$.

1. In addition to inserting $v$ into $S$, we insert all edges $e=(v,u)$ into our min-heap, with their weights as the key.
2. To get the min-weight edge, we simply extract the minimum.
3. When we add vertex $u$ to $S$, we remove all edges adjacent to $u$ that lead to a vertex back in $S$ from the min-heap, and we add all outgoing edges from $u$ to the min-heap.

Runtime

We run the primary loop once for every vertex, where $n=|V|$. Here, we extract the minimum edge, which takes $O(\log n)$.

We also insert and remove edges for every vertex that we add to the cut, which depends on the degree of the vertex. However, we do this once for every vertex, so this value is just equal to $2m$, where $m=|E|$.

Then runtime is given by $(n-1)\log n+{\sum }_{v\in V}deg(v)\log m=O(n\log n+m\log m)$.

CIS 1600 showed another way of using min-heaps that allows us to collapse the runtime down to $O(n\log n)$… instead of storing the edges in the heap, store the vertices.

Kruskal’s algorithm

1. Initialize empty set $T$, and have each vertex be in its own connected component.
2. Sort the edges according to their weight.
3. Iterate through the edges in order. Given edge $e=(u,v)$, we check if vertices $u$ and $v$ are already connected in our connected component. If not, then we include $e$ in $T$, and merge the connected components that $u$ and $v$ belong to. Otherwise, we don’t add it.

Proof of correctness: using the cut property

When we iterate through the edges and we’re currently on edge $e=(u,v)$, we can treat the set that $u$ belongs to as the cut $S$, and the other vertices belong in $V-S$. Then we can argue with the cut property that the MST must include $e$, because we’ve sorted the edges by weight, so $e$ is the current minimum-weight edge.

Usage of union-find

How do we efficiently check if $u$ and $v$ are already connected? How do we efficiently merge connected components?

Storing our vertices in a disjoint-set data structure allows us to perform queries on two vertices in an efficient manner, and merge two connected components in a trivial manner. This allows us to perform queries in at most $O(\log n)$ time, meaning that sorting the edges will dominate the overall time complexity: $O(m\log m)$.