所有最小生成树的实现

Question

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

我只能找到Kruskal算法和Prim算法的实现，它们都只返回一个MST。

我看过一些解决这个问题的论文（比如Representing all minimum spanning trees with applications to counting and generation），但是我的脑袋在想如何把它翻译成代码时，总有爆炸的倾向。

事实上我找不到任何语言的实现！

Answer 1

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

Answer 2

我不知道这是不是解决方案，但这是解决方案（我想说，这是蛮力的图形版本）：

1. 使用kruskal或prim算法查找图的MST。这应该是O（E log V）。
2. 生成所有生成树。这可以在O(Elog(V) + V + n) for n = number of spanning trees中完成，据我从2分钟的google了解，这可能会得到改进。
3. 按树的权重等于MST的权重筛选步骤2中生成的列表。这应该是n的O（n）作为步骤2中生成的树的数量。

注意：懒洋洋的！生成所有可能的树，然后过滤结果将占用O（V^2）内存，多项式空间要求是有害的-生成树，检查其权重，如果是MST，将其添加到结果列表中，如果不是-丢弃它。
总时间复杂度：O(Elog(V) + V + n) for G(V,E) with n spanning trees

Answer 3

你可以在Sorensen and Janssens (2005)的作品中找到一个想法。

其思想是按递增的顺序生成STs，一旦得到ST的较大值，就停止枚举。