c++ - 克鲁斯卡尔算法解释

Question

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

if that edge connects two different trees, then add it to the forest, combining two trees into a single tree.

所以我猜它会检查两棵不同的树是否相连，但这到底是什么意思？

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 non-trivial edges，也就是一棵树的边数。