All minimum spanning trees implementation

问题:

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!

回答1:

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):

1. Find the MST of the graph using kruskal's or prim's algorithm. This should be O(E log V).
2. 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.
3. 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

回答2:

Rubys gives a good general answer. But writing efficient code to generate all spanning trees of a graph is a beast of a challenge.

Half way down this page, at around Dec 2003, you'll find an CWEB implementation of Knuth's algorithm that finds all spanning trees of a given graph.

回答3:

Ronald Rivest has a nice implementation in Python, mst.py

回答4:

You can find an idea in the work of Sorensen and Janssens (2005).

The idea is to generate the STs in the increasing order, and as soon as you get the bigger value of ST stop the enumeration.