如何从图中有效地生成所有可能的生成树 [英] How to efficiently generate all possible spanning trees from a graph
问题描述
首先请注意,这个问题是不询问 MST ,而只是所有可能的生成树
。
First please note that this question is NOT asking about MST, instead, just all possible spanning trees
.
我只需要生成所有可能的生成树
从图中。
I just need to generate all possible spanning trees
from a graph.
我认为强力的方式是直的:
I think the brute-force way is straight:
假设我们有 V
节点和 E
边缘。
Suppose we have V
nodes and E
edges.
- 获取图形的所有边缘
- 从
E中获取
边缘。V-1
的所有可能组合 - 从组合中过滤出
非生成树
(对于生成树,所有节点在一组V-1
边缘之间应该出现一次)
- Get all edges of the graph
- Get all possible combinations of
V-1
out ofE
edges. - Filter out
non-spanning-tree
out of the combinations (for a spanning tree, all nodes inside one set ofV-1
edges should appear exactly once)
但是我认为当面对大图时太慢了。
But I think it is too slow when facing big graph.
我们有更好的方法吗?
推荐答案
将所有边的权重设置为相同的值,然后使用算法查找所有最小生成树。因为所有的生成树都有 | V | -1
边和所有的边权重相等,所有生成树将是最小生成树。
Set the weight of all edges to the same value, then use an algorithm to find all minimum spanning trees. Since all spanning trees have |V|-1
edges and all edge weights are equal, all spanning trees will be minimum spanning trees.
这篇关于如何从图中有效地生成所有可能的生成树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!