如何从图形中有效地生成所有可能的生成树

Question

首先请注意,这个问题是不是问MST,相反,只是all possible spanning trees.

因此,这是不一样的找出所有最小生成树或最小生成树实现

---

我只需spanning trees要从图中生成所有可能的东西.

我认为蛮力的方式很直接:

假设我们有V节点和E边.

1. 获取图表的所有边缘
2. 获得所有可能V-1的E边缘组合.
3. 从non-spanning-tree组合中过滤掉(对于生成树,一组V-1边内的所有节点应恰好出现一次)

但是我认为面对大图时它太慢了.

我们有更好的方法吗？

Answer 1

将所有边的权重设置为相同的值,然后使用算法查找所有最小生成树.由于所有生成树都有|V|-1边缘且所有边缘权重相等,因此所有生成树将是最小生成树.