How to efficiently generate all possible spanning trees from a graph

Question

First please note that this question is NOT asking about MST, instead, just all possible spanning trees.

So this is NOT the same as finding all minimal spanning trees or All minimum spanning trees implementation

---

I just need to generate all possible spanning trees from a graph.

I think the brute-force way is straight:

Suppose we have V nodes and E edges.

1. Get all edges of the graph
2. Get all possible combinations of V-1 out of E edges.
3. Filter out non-spanning-tree out of the combinations (for a spanning tree, all nodes inside one set of V-1 edges should appear exactly once)

But I think it is too slow when facing big graph.

Do we have a better way?

Answer 1

Set the weight of all edges to the same value, then use an algorithm to find all minimum spanning trees. Since all spanning trees have |V|-1 edges and all edge weights are equal, all spanning trees will be minimum spanning trees.

Answer 2

I've become interested in this question, and have yet to find a really satisfactory answer. However, I have found a number of references: Knuth's Algorithms S and S' in TAOCP Volume 4 Fascicle 4, a paper by Sorensen and Janssens, and GRAYSPAN, SPSPAN, and GRAYSPSPAN by Knuth. It's too bad none of them are implementations in a language I could use ... I guess I'll have to spend some time coding these ...