6

Possible Duplicate:
All minimum spanning trees implementation

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

Community
  • 1
  • 1
  • 1
    Note the number of minimum spanning trees can be exponential in the graph size, so you probably don't want to return them all. – Keith Randall Dec 31 '10 at 17:25
  • 1
    @keith Knuth wrote a whole [book](http://www.amazon.com/Computer-Programming-Fascicle-Trees-History-Combinatorial/dp/0321335708) 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. – David Nehme Sep 25 '11 at 19:51

3 Answers3

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.

Dervin Thunk
  • 19,515
  • 28
  • 127
  • 217
0

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.

David Nehme
  • 21,379
  • 8
  • 78
  • 117
-1

you can find one..modifying the BFS algorithm!

madCode
  • 3,733
  • 5
  • 26
  • 31