1

我正在阅读 wikipeida 并发现 Kruskal 的伪代码如下：

KRUSKAL(G):    
    foreach v ∈ G.V:    
        MAKE_SET(v)    
    G.E = sort(G.E)    
    i = 0    
    while (i != |V|-1):      
        pick the next (u, v) edge from sorted list of edges G.E        
        if (FIND_SET(u) != FIND_SET(v)):          
            UNION(u, v)        
            i = i + 1

我不确定是什么FIND_SET()，维基百科有以下描述：

如果该边连接两棵不同的树，则将其添加到森林中，将两棵树组合成一棵树。

所以我想它会检查是否连接了两棵不同的树，但这到底意味着什么？

4

4 回答 4

5

最初，每个顶点都在一个集合中：{v}每个顶点都有一个单例集合v。在伪代码中，这些集合是make_set(v).

对于给定的顶点v，该函数find_set(v)为您提供包含 的集合v。

该算法迭代地合并集合，因此如果{u},{v}最初是单例集合并且存在一条边(u, v)，则该算法用它们的并集替换这两个集合{u, v}。现在两者都find_set(u)将find_set(v)返回该集合。

该算法在您添加|V| - 1非平凡边后终止，这正是树中的边数。

于 2012-11-30T23:26:47.637 回答
0

FIND_SET(x) 找到与边 x 关联的集合，因此比较：

FIND_SET(u) != FIND_SET(v)

确保 u 和 v 没有连接到同一事物。一种有用的思考方式是它找到 u 和 v 的“值”，其中值本身就是集合。

关于合并森林的部分与 FIND_SET 无关，而是下一行：

UNION(u,v)

这合并了两组。

于 2012-11-30T23:26:06.480 回答
0

这find_set()是一种称为Union-Find的数据结构的常见操作。这个数据结构的想法是有不相交的集合（在你的例子中是顶点）。

在这个算法中，我认为每个集合代表连接的顶点。

因此，当您调用find_set()传递顶点时，您将收到表示该连接顶点集的元素。

于 2012-11-30T23:28:20.800 回答
0 
find_set(u)!=find_set(v)

表示生成树的基本属性，即它不产生循环。如果它们相等，则表明图中存在循环。

我们基本上通过 Kruskal 算法制作了一个森林（具有最小边权重），并在每一步检查它是否在循环。

希望能帮助到你 ：）

于 2012-12-01T07:56:32.980 回答