图有两/三不同的最小生成树？ [英] Graph Has Two / Three Different Minimal Spanning Trees ?

问题描述

我试图找到检测一个给定的图G是否具有两种不同的最小生成树的有效方法。我也想找到一种方法来检查是否有3个不同的最小生成树。 ，我已经虽然关于幼稚溶液运行Kruskal算法一次并找到最小生成树的总重量。以后，除去的边缘从该图并再次运行Kruskal算法，并检查是否新的树的重量是原始最小生成树的重量，并因此在图中的每个边缘。运行时是O（| V || E |登录| V |）。这是不擅长的一切，我觉得有一个更好的方式来做到这一点。

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

任何建议将是有益的， 在此先感谢

Any suggestion would be helpful, thanks in advance

推荐答案

您可以修改Kruskal算法来做到这一点。

You can modify Kruskal's algorithm to do this.

首先，边缘（重量）排序。然后，对于以升序每个权重，过滤掉所有不相干边缘。有关的边缘上形成的最小跨度林那么远的连接的部件的曲线图。可以计数该图生成树的数目。取本品对所有的重量，你已经计算在图中的最小生成树的总数。

First, sort the edges by weight. Then, for each weight in ascending order, filter out all irrelevant edges. The relevant edges form a graph on the connected components of the minimum-spanning-forest-so-far. You can count the number of spanning trees in this graph. Take the product over all weights and you've counted the total number of minimum spanning trees in the graph.

您恢复相同的运行时间Kruskal算法，如果你只关心一棵树，两棵树，和三个或更多的树的情况。我想你风做一个行列式计算什么的枚举一般生成树，所以你可能会风与一个O（MM（n））的最坏情况一般。

You recover the same running time as Kruskal's algorithm if you only care about the one-tree, two-trees, and three-or-more-trees cases. I think you wind up doing a determinant calculation or something to enumerate spanning trees in general, so you likely wind up with an O(MM(n)) worst-case in general.

这篇关于图有两/三不同的最小生成树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！