EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
Akiyoshi Shioura, Akihisa Tamura · Journal of the Operations Research Society of Japan · 1995
Let G be an undirected graph with V vertices and E edges. We consider the problem of enumerating all spanning trees of G. In order to explicitly output all spanning trees, the output size is of Θ(NV), where N is the number of spanning trees. This, however, can be compressed into Θ(N) size. In this paper, we propose a new algorithm for enumerating all spanning trees of G in such compact form. The time and space complexities of our algorithm are O(N + V + E) and O(VE), respectively. The algorithm is optimal in the sense of time complexity.