## Prim’s algorithm

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

- Initialize cut $S={v}$ for any arbitrary $v∈V$ and the tree $T=∅$ to begin with.
- Find the min-weight edge $e$ such that $e=(v,u)$ and it crosses $(S,V−S)$ over all the vertices in $S$.
- Update $S←S∪{u}$, and add $e$ to $T$.
- 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$.

- In addition to inserting $v$ into $S$, we insert all edges $e=(v,u)$ into our min-heap, with their weights as the key.
- To get the min-weight edge, we simply extract the minimum.
- 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(gn)$.

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)gn+∑_{v∈V}deg(v)gm=O(ngn+mgm)$.

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

## Kruskal’s algorithm

- Initialize empty set $T$, and have each vertex be in its own connected component.
- Sort the edges according to their weight.
- 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(gn)$ time, meaning that sorting the edges will dominate the overall time complexity: $O(mgm)$.