python - All minimum spanning trees implementation

Question

I've been looking for an implementation (I'm using networkx library.) that will find all the minimum spanning trees (MST) of an undirected weighted graph.

I can only find implementations for Kruskal's Algorithm and Prim's Algorithm both of which will only return a single MST.

I've seen papers that address this problem (such as Representing all minimum spanning trees with applications to counting and generation) but my head tends to explode someway through trying to think how to translate it to code.

In fact i've not been able to find an implementation in any language!

What do you need this for? I imagine doing it efficiently won't be trivial, so is generating all the subsets of n - 1 edges too slow? — IVlad
I'm implementing an algorithm from this paper (linkinghub.elsevier.com/retrieve/pii/S1571065309002066), one of the required steps is to iterate through all mst. — russtbarnacle
Hi! Not to revive an old thread, but I'm looking for an implementation (in any language) of an algorithm that will give me all spanning trees of a graph. This is very similar to what you were looking for. Did you have any success? — rjkaplan
One simple idea that comes to mind is a slight modification of Kruskal's algorithm that would at each selection step iterate over all candidate edges (i.e. all min-weight, yet unselected edges that do not create a cycle in the growing forest) instead of picking an arbitrary one. — Anthony Labarre

Rubys Rubys · Accepted Answer · 2010-05-29T23:38:47

I don't know if this is the solution, but it's a solution (it's the graph version of a brute force, I would say):

Find the MST of the graph using kruskal's or prim's algorithm. This should be O(E log V).
Generate all spanning trees. This can be done in O(Elog(V) + V + n) for n = number of spanning trees, as I understand from 2 minutes's worth of google, can possibly be improved.
Filter the list generated in step #2 by the tree's weight being equal to the MST's weight. This should be O(n) for n as the number of trees generated in step #2.

Note: Do this lazily! Generating all possible trees and then filtering the results will take O(V^2) memory, and polynomial space requirements are evil - Generate a tree, examine it's weight, if it's an MST add it to a result list, if not - discard it.
Overall time complexity: O(Elog(V) + V + n) for G(V,E) with n spanning trees

python - All minimum spanning trees implementation

3 Answers