Kruskal的算法解释

Question

我正在阅读wikipeida并发现Kruskal的Pseudocode如下:

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非平凡边之后,算法终止,这正是树中边的数量.