Search for all minimal spanning trees

Question

Possible duplicate:
All minimal spanning tree implementations

How can I find all minimal spanning trees in an undirected graph in an efficient way?

Answer 1

Apologies for the academic response ... but the algorithm Sin Knuth TAOCP , Volume 4, Fascicle 4 is precisely about generating all spanning trees (p. 26ff). There are some musings when he talks about spanning trees, but your best bet is TAOCP.

Answer 2

you can find one ... BFS algorithm!

Answer 3

Yes, there are algorithms for creating all spanning trees in a graph. At least one compresses the output, generating only differences between trees. As others have pointed out, for even a small graph there can be many minimal spanning trees.