11

First please note that this question is NOT asking about MST, instead, just all possible spanning trees.

So this is NOT the same as finding all minimal spanning trees or All minimum spanning trees implementation

I just need to generate all possible spanning trees from a graph.

I think the brute-force way is straight:

Suppose we have V nodes and E edges.

  1. Get all edges of the graph
  2. Get all possible combinations of V-1 out of E edges.
  3. Filter out non-spanning-tree out of the combinations (for a spanning tree, all nodes inside one set of V-1 edges should appear exactly once)

But I think it is too slow when facing big graph.

Do we have a better way?

Community
  • 1
  • 1
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
  • 1
    Actually the algorithm you link to will work for you after you set all edge weights to the same value. Most obvious choice for weights would be 1 or 0, but it's entirely irrelevant (apart from overflow issues if there are any). – G. Bach Mar 02 '14 at 14:13
  • @G.Bach could you please transform your comment to an answer? – Jackson Tale Mar 02 '14 at 14:53

2 Answers2

10

Set the weight of all edges to the same value, then use an algorithm to find all minimum spanning trees. Since all spanning trees have |V|-1 edges and all edge weights are equal, all spanning trees will be minimum spanning trees.

G. Bach
  • 3,869
  • 2
  • 25
  • 46
  • 2
    I suppose that this is a correct answer, but it recalls to me [the joke about a mathematician boiling water](http://www-users.cs.york.ac.uk/susan/joke/3.htm#boil) because every MST enumeration algorithm that I know of enumerates all spanning trees in the subgraph of safe edges. – David Eisenstat Mar 02 '14 at 16:22
  • 1
    @DavidEisenstat I've never had a look at any algorithm enumerating MSTs, so only having that as a black box, the obvious approach is my answer. I do like that joke, though. Not sure whether it's making fun of engineers or mathematicians, or both. EDIT: thanks for that website, haven't laughed like that in a while. – G. Bach Mar 02 '14 at 16:29
  • @DavidEisenstat do you have any better idea? – Jackson Tale Mar 02 '14 at 19:52
  • @JacksonTale I don't know what algorithms to enumerate MSTs are out there, but considering that all the ones David knows enumerate all spanning trees of some subset, you might want to have a look at those in detail and just throw out the restrictions limiting the algorithm to the safe edges. – G. Bach Mar 02 '14 at 23:57
  • 1
    @JacksonTale I somehow got it into my head that David Eppstein's 1995 paper (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8848) was simpler than it actually is. There's an algorithm for generating spanning trees in Knuth's Volume 4 of TAoCP. – David Eisenstat Mar 04 '14 at 13:52
  • A BFS or DFS also would allow enumeration of spanning trees no need for MST algorithms – Gregory Morse Mar 27 '21 at 08:36
  • -1 because this answer basically says, "to enumerate all spanning trees, simply use an algorithm that enumerates all spanning trees". That is not useful. Generating each spanning tree precisely once (i.e. making sure that you get all of them without creating duplicates) is not exactly trivial. – Szabolcs Nov 01 '21 at 15:39
3

I've become interested in this question, and have yet to find a really satisfactory answer. However, I have found a number of references: Knuth's Algorithms S and S' in TAOCP Volume 4 Fascicle 4, a paper by Sorensen and Janssens, and GRAYSPAN, SPSPAN, and GRAYSPSPAN by Knuth. It's too bad none of them are implementations in a language I could use ... I guess I'll have to spend some time coding these ...

Edward Doolittle
  • 4,002
  • 2
  • 14
  • 27