0

通过在网上搜索，我可以找到 2（kruskal 和 prims）算法来查找最小生成树。但是这个算法

   *let T be initially the set of all edges
       *while there is some cycle C in T
         remove edge e from T where e has the heaviest weight in C

我通过网络搜索找不到。我如何实现这个算法。我怎样才能找到每一个可能的循环？

4

2 回答 2

1

按降序对边进行排序，然后每次尝试删除一条边。检查图形是否连通。如果删除一条边后图仍然是连通的，则保证该边在一个循环中。

于 2013-10-22T12:29:17.423 回答
1

实现这一点的最简单方法是通过 Union-Find 数据结构（见下面的链接）。检查周期可以在 O(1) 时间内完成，添加一条新边平均每个节点需要 O(log V) 处理，需要 O(E + V log V) 的总体运行时间。我们可以使用更高级的数据结构来实现接近线性的时间界限。

http://people.cs.umass.edu/~barring/cs611/lecture/7.pdf

于 2013-12-02T07:38:18.580 回答