All minimum spanning trees implementation

python algorithm language-agnostic graph-theory minimum-spanning-tree
russtbarnacle picture russtbarnacle · May 29, 2010 · Viewed 14.7k times · Source

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!

Answer

Rubys picture Rubys · May 30, 2010

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

Related questions

Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More
How to generate all permutations of a list?

How do you generate all the permutations of a list in Python, independently of the type of elements in that list? For example: permutations([]) [] permutations([1]) [1] permutations([1, 2]) [1, 2] [2, 1] permutations([1, 2, 3]) [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Read More
Check if all elements in a list are identical

I need a function which takes in a list and outputs True if all elements in the input list evaluate as equal to each other using the standard equality operator and False otherwise. I feel it would be best to …

Read More