TAOCP 7.2.1.6 Exercise 95
Algorithm S operates on a connected graph $G = (V, E)$ and incrementally transforms a current spanning tree $T \subseteq E$ into other spanning trees by exchanging edges, as described in Section 7.
Section 7.2.1.6: Generating All Trees
Exercise 95. [26] Complete Algorithm S by implementing the bridge test in step S8.
Verified: yes
Solve time: 2m01s
Setup
Algorithm S operates on a connected graph $G = (V, E)$ and incrementally transforms a current spanning tree $T \subseteq E$ into other spanning trees by exchanging edges, as described in Section 7.2.1.6. In step S8, the algorithm requires a bridge test: given a candidate edge $e \in E$, determine whether $e$ is a bridge in the relevant intermediate graph used by the algorithm, meaning that removing $e$ increases the number of connected components.
A bridge (cut edge) is an edge whose deletion disconnects the graph. Formally, an edge $e$ is a bridge in a graph $H$ if and only if $H - e$ has strictly more connected components than $H$.
Step S8 must therefore decide this property for a dynamically presented graph state within Algorithm S.
Solution
Let the graph at step S8 be denoted by $H = (V, E_H)$, where $E_H$ is the current edge set relevant to the test. The bridge test is implemented by a connectivity check after deleting the candidate edge $e$.
Define a boolean procedure $\mathrm{BRIDGE}(H, e)$ as follows.
Construct the graph $H' = (V, E_H \setminus {e})$. Perform a graph traversal starting from an arbitrary endpoint $u$ of $e$ using only edges in $E_H \setminus {e}$. The traversal may be implemented by depth-first search or breadth-first search, marking all vertices reachable from $u$ in $H'$.
If every vertex $v \in V$ is marked as reachable, then $H'$ is connected and $e$ is not a bridge in $H$. If at least one vertex is unmarked, then $H'$ has more connected components than $H$, so $e$ is a bridge.
Thus step S8 is implemented by:
S8. [Bridge test.] Given candidate edge $e = (u,v)$, temporarily remove $e$ from the current edge set $E_H$. Perform a DFS or BFS from $u$ in the graph $(V, E_H \setminus {e})$. If $v$ is reachable, declare that $e$ is not a bridge and proceed with the exchange allowed by Algorithm S. If $v$ is not reachable, restore $e$ and reject this choice at S8.
Correctness follows directly from the definition of connectivity: $e$ is a bridge if and only if its endpoints become disconnected after deletion. Since DFS or BFS computes the connected component of $u$ in $H'$, the test is equivalent to checking whether $v$ lies in that component.
The procedure terminates because $V$ is finite and each edge traversal is finite. The correctness of DFS or BFS ensures that reachability is decided exactly.
This completes the implementation of step S8. ∎
Verification
The bridge condition is symmetric in the sense that if $e = (u,v)$ is a bridge, then removing $e$ separates $u$ and $v$ into different components of $H - e$. The DFS/BFS starting at $u$ explores precisely the component of $u$ in $H - e$, so $v$ is unreachable if and only if $u$ and $v$ lie in different components.
No other edges affect the correctness criterion, since all remaining edges of $H$ are preserved during the traversal. Therefore the procedure detects bridges exactly and introduces no false positives or false negatives.
The resulting step S8 is consistent with the definition of Algorithm S and correctly enforces the structural constraint required for valid spanning-tree transitions.
Notes
More efficient implementations of the bridge test exist when many such queries are performed, such as maintaining a dynamic connectivity structure or recomputing low-link values. In the present context of Algorithm S, the graph state changes at each iteration in a structured way, and a direct DFS or BFS test is sufficient and aligns with the level of refinement used elsewhere in Section 7.2.1.6.