TAOCP 7.2.1.6 Exercise 94
Algorithm S operates by transforming one spanning tree into another while maintaining a valid spanning tree structure throughout its execution.
Section 7.2.1.6: Generating All Trees
Exercise 94. [22] Algorithm S needs to "prime the pump" by finding an initial spanning tree in step S1. Explain how to do that task.
Verified: yes
Solve time: 2m14s
Solution
Algorithm S operates by transforming one spanning tree into another while maintaining a valid spanning tree structure throughout its execution. The mechanism assumes that an initial spanning tree of the input graph is already available in step S1, since the subsequent replacement steps modify an existing tree rather than constructing one from scratch.
Let the underlying graph be $G = (V,E)$, assumed connected, since otherwise spanning trees are replaced by spanning forests and the same initialization argument applies componentwise. Step S1 therefore reduces to constructing any spanning tree $T_0 \subseteq E$ with $|T_0| = |V| - 1$.
A direct construction is obtained by a depth-first search started from an arbitrary root vertex $v_0 \in V$. Maintain a set $S$ of visited vertices, initially $S = {v_0}$, and a set $T_0$ of selected edges, initially empty. Whenever the search moves from a vertex $u \in S$ to a vertex $v \notin S$ along an edge $(u,v) \in E$, the vertex $v$ is inserted into $S$ and the edge $(u,v)$ is inserted into $T_0$. The search continues until every vertex lies in $S$.
Each vertex $v \neq v_0$ is inserted into $S$ exactly once, and at that moment exactly one incident edge is added to $T_0$. Hence exactly $|V| - 1$ edges are selected. Since every vertex is reached from $v_0$ by a unique discovery path contained in $T_0$, the subgraph $(V,T_0)$ is connected. A connected graph on $|V|$ vertices with $|V| - 1$ edges is a tree, so $T_0$ is a spanning tree of $G$.
The same construction is obtained if depth-first search is replaced by breadth-first search, since each newly discovered vertex is attached by a single previously unused edge and no cycles are created. Either method produces a valid initial state for Algorithm S in linear time in $|V| + |E|$.
Thus step S1 is implemented by any standard traversal that grows a tree by first-visit edges, and the resulting edge set provides the required starting spanning tree for the generation process of Algorithm S.
This completes the proof. ∎