克鲁斯卡尔的算法解释

Question

我正在阅读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()是做什么的，维基百科有以下描述：

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

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

Answer 1

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

对于给定的顶点v，函数find_set(v)给你包含v的集合。

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

在您

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

Answer 2

find_set()是一种称为 Union-Find 的数据结构的常见操作。此数据结构的想法是具有不相交集（在您的示例中为顶点）。

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

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

Answer 3

FIND_SET（x） 查找与边 x 关联的集合，以便比较：

FIND_SET(u) != FIND_SET(v)

确保 u 和 v 未连接到同一事物。 一个有用的思考方式是，它找到u和v的"值"，其中值本身是集合的。

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

UNION(u,v)

合并了两组。

Answer 4

find_set(u)!=find_set(v) 

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

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

希望对:)有所帮助