An Algorithm for Finding All the Spanning Trees in Undirected Graphs
Tomomi Matsui · 1998
: In this paper, we propose an algorithm for finding all the spanning trees in undirected graphs. The algorithm requires O(n + m + øn) time and O(n + m) space, where the given graph has n vertices, m edges and ø spanning trees. For outputting all the spanning trees explicitly, this algorithm is optimal. 1 Introduction This paper considers a problem for finding all the spanning trees in undirected graphs. This problem has a long history and a lot of algorithms have been proposed (e.g., [4, 5, 9]). In 1975, Read and Tarjan presented an algorithm by using a technique called backtracking [7]. Their algorithm requires O(n +m + øm) time and O(n +m) space, where the given graph has n vertices, m edges and ø spanning trees. In [3], Gabow and Myers refined the backtracking approach and obtained an algorithm with O(n+m+øn) time and O(n+m) space. For outputting all the spanning trees explicitly, this algorithm is optimal. In this paper, we propose an algorithm which generates all the spanning ...