1

I have a small graph (<30 edges) with many edges with only 3 possible lengths.

In order to get an optimal tree, I started to find the minimum spanning tree. But there is a strong probability that there are several solutions for this, and in this case, I want to get all the minimum spanning trees, in order to apply an other custom filter.

Let's start with an example:

  • ab = 3
  • bc = 3
  • ac = 2
  • ad = 3
  • cd = 1

Here, possible MSTs are ac, cd, ab and ac, cd, bc.

I started to find them with Kruskal, where we need to sort edges by length first.

I had the idea to find all possible sorted lists, then applying Kruskal for each of them. More precisely, I group edges by lengths, then I find all possible permutations for each group. For the example below, all possible sorted lists are:

  • ab, bc, ad, ac, cd
  • ab, ad, bc, ac, cd
  • bc, ab, ad, ac, cd
  • bc, ad, ab, ac, cd
  • ad, ab, bc, ac, cd
  • ad, bc, ab, ac, cd

It works. For this small graph.

But if I try this with a graph with 10 edges of same length, there is several millions of possible permutations, and applying Kruskal for each of them is not really optimized.

Any idea?

roipoussiere
  • 5,142
  • 3
  • 28
  • 37

1 Answers1

1

You can do in many possible way, you need to use Kruskal or prims algorithm and modify them, such that every time you find edges with the same weight you do a recursion and restart a new tree from the actual vertex.

Return all the possible MST it is not efficient, think to a fully connected graph that has all the edges with same weight. There will be `O(n^n) possible trees.

A lot of tree will have some equal part so you can find a better solution, but you still need to return them all and this is not efficient.

You can read this paper for more Algorithm for Enumerating All Spanning Trees of Undirected and Weighted Graphs or a python implementation

mini
  • 180
  • 10