Prim's algorithm

Remarks

Example: let $G$ be the triangle on $\set{a, b, c}$ with $w(ab) = 1$, $w(bc) = 2$, $w(ac) = 3$, and let $r = a$. The first step picks $ab$ (weight $1$ beats $3$), and the second picks $bc$ (weight $2$ beats $3$). The result $\set{ab, bc}$ is a spanning tree of least weight $3$.

Non-example: if $G$ is not connected, step 2 eventually finds no edge leaving $S$ while $S \ne V$. The algorithm then only spans the component of $r$.

Correctness follows from the cut property applied to the partition $(S, V \setminus S)$. With a binary heap the running time is $O(m \log n)$, and with a Fibonacci heap it is $O(m + n \log n)$, where $n = \abs{V}$ and $m = \abs{E}$.