How to efficiently generate all possible spanning trees from a graph

Question

Please note first that this question does NOT ask a question about MST , but simply all possible spanning trees.

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

---

I just need to generate everything possible spanning treesfrom the graph.

I think the brute force method is direct:

Suppose we have Vnodes and Eedges.

• Get all edges of a graph
• Get all possible combinations V-1of Eribs.
• Filter non-spanning-treeout combinations (for the spanning tree, all nodes within the same set of edges V-1should be displayed exactly once)

But I think it is too slow when faced with a large schedule.

Do we have a better way?

Answer 1

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

Answer 2

. , : S S ' TAOCP Volume 4 Fascicle 4, a GRAYSPAN, SPSPAN GRAYSPSPAN Knuth. , , ... , ...