Search code examples
algorithmgraphminimum-spanning-tree

finding all minimal spanning trees

Possible Duplicate:
All minimum spanning trees implementation

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

Solution

  • 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.