Efficiently scanning all spanning trees of an undirected graph

Let G be an undirected graph with V vertices and E edges. The authors 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, the authors propose a new algorithm for enumerating all spanning trees of G in such compact form. The time and space complexities of the present algorithm are O(N+V+E) and O(VE), respectively. The algorithm is optimal in the sense of time complexity.