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?

Ligament

Note the number of minimum spanning trees can be exponential in the graph size, so you probably don't want to return them all. – Venatic

@keith Knuth wrote a whole book about enumerating trees in graphs. Just because you have an exponential number of something doesn't mean you don't want to see them all. In this case it just means it's not practical so see all of them for a general large graph. – Griskin

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.

Bluenose

Answer 2

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.

Griskin

Answer 3

you can find one..modifying the BFS algorithm!

Mccurdy