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.
How to efficiently generate all possible spanning trees from a graph
-
19-10-2022 - |
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.
- Get all edges of the graph
- Get all possible combinations of
V-1
out ofE
edges. - Filter out
non-spanning-tree
out of the combinations (for a spanning tree, all nodes inside one set ofV-1
edges should appear exactly once)
But I think it is too slow when facing big graph.
Do we have a better way?
Solution
OTHER TIPS
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 ...