python - 所有最小生成树实现

Question

我一直在寻找一种实现（我正在使用networkx库。）它将找到无向加权图的所有最小生成树（MST）。

我只能找到 Kruskal 算法和 Prim 算法的实现，这两种算法都只会返回一个 MST。

我看过解决这个问题的论文（例如Representing all minimum spanning trees with applications to count and generation），但我的脑袋往往会因为试图思考如何将其转换为代码而爆炸。

事实上，我无法找到任何语言的实现！

Answer 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

Answer 2

Ronald Rivest 在 Python 中有一个很好的实现，mst.py

Answer 3

您可以在Sorensen 和 Janssens (2005)的工作中找到一个想法。

这个想法是按递增的顺序生成 ST，一旦你得到更大的 ST 值，就停止枚举。