Finding All Spanning Trees of Directed and Undirected Graphs
- 1 August 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 7 (3) , 280-287
- https://doi.org/10.1137/0207024
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, andN 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