finding all minimal spanning trees [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

All minimum spanning trees implementation

How can I find all minimum spanning t开发者_Python百科rees in an undirected graph in an efficient way?

---

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.

---

you can find one..modifying the BFS algorithm!

---

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.