TAOCP 2.3.4.1 Exercise 11
Let $S$ be any nonempty proper subset of the terminals, and let $\bar S$ be its complement.
Exercise 11. [**] $$M27$$ (R. C. Prim, Bell System Tech. J. 36 (1957), 1389-1401.) Consider the wire connection problem of exercise 10 with the additional proviso that a cost $c(i,j)$ is given for each $i<j$, denoting the expense of wiring terminal $T_i$ to terminal $T_j$. Show that the following algorithm gives a connection tree of minimum cost: "If $n=1$, do nothing. Otherwise, renumber terminals ${1,\ldots,n-1}$ and the associated costs so that $c(n-1,n)=\min_{1\le i<n} c(i,n)$; connect terminal $T_{n-1}$ to $T_n$; then change $c(j,n-1)$ to $\min(c(j,n-1),c(j,n))$ for $1\le j<n-1$, and repeat the algorithm for $n-1$ terminals $T_1,\ldots,T_{n-1}$ using these new costs. (The algorithm is to be repeated with the understanding that whenever a connection is subsequently requested between the terminals now called $T_j$ and $T_{n-1}$, the connection is actually made between terminals now called $T_j$ and $T_n$ if it is cheaper; thus $T_{n-1}$ and $T_n$ are being regarded as though they were one terminal in the remainder of the algorithm.)" This algorithm may also be stated as follows: "Choose a particular terminal to start with; then repeatedly make the cheapest possible connection from an unchosen terminal to a chosen one, until all have been chosen."
Fig. 33. Free tree of minimum cost. (See exercise 11.)
For example, consider Fig. 33(a), which shows nine terminals on a grid; let the cost of connecting two terminals be the wire length, namely the distance between them. (The reader may wish to try to find a minimal cost tree by hand, using intuition instead of the suggested algorithm.) The algorithm would first connect $T_8$ to $T_9$, then $T_6$ to $T_8$, $T_5$ to $T_6$, $T_2$ to $T_6$, $T_1$ to $T_2$, $T_3$ to $T_1$, $T_7$ to $T_3$, and finally $T_4$ to either $T_2$ or $T_6$. A minimum cost tree (wire length $7+2\sqrt2+2\sqrt5$) is shown in Fig. 33(b).
Verified: yes
Solve time: 42s
Let $S$ be any nonempty proper subset of the terminals, and let $\bar S$ be its complement. Any connection tree must contain at least one wire joining a terminal of $S$ to a terminal of $\bar S$, since otherwise the terminals in $S$ could not be connected to those in $\bar S$. Let $(u,v)$ be the cheapest such wire. We claim that some minimum-cost connection tree contains $(u,v)$. For if a minimum-cost tree $T$ does not contain $(u,v)$, adding $(u,v)$ to $T$ creates a cycle. That cycle contains another edge $(x,y)$ joining $S$ to $\bar S$; since $(u,v)$ is the cheapest such edge, $c(u,v)\le c(x,y)$. Replacing $(x,y)$ by $(u,v)$ yields another connection tree whose cost is no greater than that of $T$. Hence there exists a minimum-cost tree containing $(u,v)$.
At each stage of the algorithm, the chosen terminals form a set $S$, and the next wire selected is precisely the cheapest wire joining $S$ to $\bar S$. By the preceding paragraph, some minimum-cost tree contains that wire. After the algorithm chooses the wire joining $T_{n-1}$ to $T_n$, the modification $c(j,n-1)\leftarrow\min(c(j,n-1),c(j,n))$ contracts these two terminals into a single terminal without changing the minimum possible remaining cost, because any future connection to the contracted vertex may be made through the cheaper of the two alternatives. Therefore the problem reduces to the same problem on $n-1$ terminals. By induction on $n$, the recursive algorithm constructs a minimum-cost connection tree. The equivalent formulation, starting from any terminal and repeatedly adding the cheapest connection from an unchosen terminal to a chosen one, performs exactly the same sequence of choices. This completes the proof.
∎