TAOCP 2.3.4.1 Exercise 12
A direct implementation is obtained by maintaining, for each terminal not yet in the growing tree, the cheapest known connection from that terminal to any terminal already in the tree.
Exercise 12. [**] $$29$$ The algorithm of exercise 11 is not stated in a fashion suitable for direct computer implementation. Reformulate that algorithm, specifying in more detail the operations that are to be done, in such a way that a computer program can carry out the process with reasonable efficiency.
Verified: no
Solve time: 2m11s
A direct implementation is obtained by maintaining, for each terminal not yet in the growing tree, the cheapest known connection from that terminal to any terminal already in the tree.
Choose an arbitrary terminal as the initial tree. For each terminal $T_i$ outside the tree, store a value $d_i$, equal to the minimum cost of connecting $T_i$ to a terminal already in the tree, together with the corresponding terminal $p_i$ in the tree. Repeatedly perform the following operations:
$$ k \leftarrow \text{an index for which } d_k \text{ is minimum}; $$
$$ \text{add the edge } (T_k,p_k) \text{ to the tree}; $$
$$ T_k \leftarrow \text{a terminal of the tree}; $$
For every terminal $T_j$ not yet in the tree,
$$ d_j \leftarrow \min(d_j,c(j,k)); $$
and, whenever $c(j,k)<d_j$ before the replacement,
$$ p_j \leftarrow k. $$
After $n-1$ edges have been added, the tree is complete. The replacements displayed above account for four kinds of assignments in each iteration.
With a table of the values $d_i$ and $p_i$, each iteration requires scanning the remaining terminals once to find the minimum $d_i$ and once to update the costs. Hence the running time is $O(n^2)$ and the storage requirement is $O(n)$. This is a direct computer realization of the algorithm of exercise 11, commonly called Prim's algorithm.