我一直在寻找一种实现(我正在使用 networkx 库。)它将找到无向加权图的所有最小生成树 (MST)。
我只能找到 Kruskal 算法和 Prim 算法的实现，这两种算法都只会返回一个 MST。
我看过解决这个问题的论文(例如 Representing all minimum spanning trees with applications to counting and generation )，但我的脑袋往往会因为试图将其转换为代码而以某种方式爆炸。
事实上，我找不到任何语言的实现!
最佳答案
我不知道这是否是 解决方案，但它是 一个 解决方案(我会说这是蛮力的图形版本):
- 使用 kruskal 或 prim 算法求图的 MST。这应该是 O(E log V)。
- 生成所有生成树。这可以在
O(Elog(V) + V + n) for n = 生成树数中完成，正如我从 2 分钟的 google 中了解到的那样，可能会得到改进。 - 通过树的权重等于 MST 的权重过滤步骤 #2 中生成的列表。这应该是 O(n)，因为 n 作为步骤 #2 中生成的树的数量。
注意:懒惰地做这个!生成所有可能的树然后过滤结果将占用 O(V^2) 内存，并且多项式空间要求是邪恶的 - 生成一棵树，检查它的权重，如果它是 MST，则将其添加到结果列表中，如果不是 - 丢弃它.
总体时间复杂度:O(Elog(V) + V + n) for G(V,E) with n spanning trees
关于python - 所有最小生成树实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2935754/