Search code examples
algorithmdata-structuresgraphtree

How to efficiently generate all possible spanning trees from a graph

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?

Solution

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