finding all minimal spanning trees [duplicate]

Question

Possible Duplicate:
All minimum spanning trees implementation

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

Answer 1

Apologies for the academic answer... but algorithm S in Knuth's TAOCP, Volume 4, Fascicle 4 is exactly about generating all spanning trees (pp. 26ff). There are a few musings when he talks about generating (spanning) trees, but your best bet in TAOCP.

Answer 2

you can find one..modifying the BFS algorithm!

Answer 3

Yes, there are algorithms for generating all spanning trees in a graph. At least one compresses the output by generating only diffs between the trees. As others have pointed out, there might be a lot of minimum spanning trees for even a small graph.