Finding All Spanning Trees of Directed and Undirected Graphs
Authors:
- Harold N. GabowHGHarold N. Gabow
- Eugene W. MyersEMEugene W. Myers
- 1 August 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 7 (3) , 280-287
Abstract
An algorithm for finding all spanning trees (arborescences) of a directed graph is presented. It uses backtracking and a method for detecting bridges based on depth-first search. The time required is $O(V + E + EN)$ and the space is $O(V + E)$, where V, E, and N represent the number of vertices, edges, and spanning trees, respectively. If the graph is undirected, the time decreases to $O(V + E + VN)$, which is optimal to within a constant factor. The previously best-known algorithm for undirected graphs requires time $O(V + E + EN)$.
Keywords
This publication has 7 references indexed in Scilit:
- Two Algorithms for Generating Weighted Spanning Trees in OrderSIAM Journal on Computing, 1977
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning TreesNetworks, 1975
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Algorithm 354: generator of spanning trees [H]Communications of the ACM, 1969
- Generation of Trees without DuplicationsIEEE Transactions on Circuit Theory, 1965
- A Simple Algorithm for Listing All the Trees of a GraphIEEE Transactions on Circuit Theory, 1965
- Generation and Realization of Trees and k-TreesIEEE Transactions on Circuit Theory, 1964