所有最小生成树的实现
我一直在寻找一个实现（我在使用networkx库），可以找到一个无向加权图的所有最小生成树（MST）。
我只找到克鲁斯卡尔算法和普里姆算法的实现，这两种算法只能返回一棵最小生成树。
我看到过一些论文讨论这个问题（比如表示所有最小生成树及其在计数和生成中的应用），但我在试着把这些内容转化为代码时，总是觉得脑袋要爆炸。
实际上，我在任何语言中都找不到这样的实现！
4 个回答
0
你可以在Sorensen和Janssens（2005年）的研究中找到一个想法。
这个想法是按顺序生成ST（某种数据结构），一旦你得到一个更大的ST值，就停止生成。
0
罗纳德·里维斯特在Python中有一个很不错的实现，mst.py
10
我不知道这是否是唯一的解决方案，但这是一个解决方案（我觉得这就像是图的暴力破解版本）：
- 使用克鲁斯克尔算法或普里姆算法找到图的最小生成树（MST）。这个步骤的复杂度应该是 O(E log V)。
- 生成所有的生成树。根据我在网上查的两分钟资料，这个步骤可以在
O(Elog(V) + V + n) 中完成，其中 n 是生成树的数量，可能还有改进的空间。 - 通过比较树的权重与最小生成树的权重来过滤第二步生成的列表。这个步骤的复杂度应该是 O(n)，其中 n 是第二步生成的树的数量。
注意：要懒惰地做这件事！生成所有可能的树然后再过滤结果会占用 O(V^2) 的内存，而多项式的空间需求是很麻烦的——生成一棵树，检查它的权重，如果它是最小生成树，就把它加入结果列表，如果不是，就丢弃它。
总体时间复杂度：O(Elog(V) + V + n)，对于有 n 棵生成树的 G(V,E)