所有最小生成树实现

Question

我一直在寻找一个实现(我正在使用networkx库.),它将找到无向加权图的所有最小生成树(MST).

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

我已经看到了解决这个问题的论文(比如代表所有最小的生成树以及应用程序计数和生成),但是我的脑袋往往会在尝试思考如何将其转换为代码时出现爆炸.

事实上,我无法找到任何语言的实现!

Answer 1

我不知道这是否是解决方案,但它是一个解决方案(这是蛮力的图形版本,我想说):

1. 使用kruskal或prim算法找到图形的MST.这应该是O(E log V).
2. 生成所有生成树.这可以通过O(Elog(V) + V + n) for n = number of spanning trees我从2分钟的谷歌了解,可以改善.
3. 通过树的权重等于MST的权重来过滤步骤#2中生成的列表.对于n,这应该是O(n),作为步骤#2中生成的树的数量.

注意:懒惰地这样做!生成所有可能的树然后过滤结果将需要O(V ^ 2)内存,并且多项式空间要求是邪恶的 - 生成树,检查它的权重,如果它是MST将其添加到结果列表,如果不是 - 丢弃它.
整体时间复杂度:O(Elog(V) + V + n) for G(V,E) with n spanning trees