如何从图中有效地生成所有可能的生成树 [英] 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.

1. 获取图形的所有边缘


2. 从 E中获取 V-1 的所有可能组合边缘。


3. 从组合中过滤出非生成树（对于生成树，所有节点在一组 V-1 边缘之间应该出现一次）

1. Get all edges of the graph
2. Get all possible combinations of V-1 out of E edges.
3. Filter out non-spanning-tree out of the combinations (for a spanning tree, all nodes inside one set of V-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屋！