首页 > 代码库 > 并查集小记

并查集小记


并查集:

并查集,一种树型的数据结构,处理一些不相交集合的合并及查询问题。比如问题:某个家族人员过于庞大,要判断两个人是否是亲戚,不太容易。现给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。


从基本实现集合的结构出发:


1.单纯的快速查找:

若id相同则在一个集合中,下图中,( 2, 3, 4, 9 )为一集合, 3 和 6 不在一个集合中


合并集合时,需逐个比较将两个集合的 id 统一,慢

缺陷:

合并慢

==================================================


2.单纯的快速合并:


上图,3 的祖先是 9, 5 的祖先是 6,则 3 和 5 不在一个集合中。

若要合并 3 和 5 所在集合,则任意选择一个集合的祖先接到另一个集合的祖先上去,其他节点信息不动。

如下合并 3, 5:



快速合并的过程图:


缺陷:

树增高,退化。

===================================================


3.按重合并:

将节点数小的集合拼接到节点数大的集合中去,只修改小集合的根节点的父亲,其他节点父亲不动。按重合并能保证树的平缓增长。




==================================================


4.路劲压缩:

如若找 9 的祖先,则从 9 到 0 的路径上的所有节点拼接到0上面。




=================================================


5.按重合并 加上 路径压缩(并查集):

过程图如下



C++ 代码:

#include <iostream>
#include <string.h>
using namespace std;
#define NODE_SIZE 100

int set_weights[NODE_SIZE];
int parent[NODE_SIZE];

void init(){
    for( int i = 0; i < NODE_SIZE; ++i ){
        set_weights[i] = 1;
        parent[i] = i;
    }
}

// 寻找改点的祖先 当该点的值 等于 本身的父亲 才是集合的根,返回
int find_ancestor( int i ){
    if( i != parent[i] )
        parent[i] = find_ancestor( parent[i] );
    return parent[i];
}

void merge_set( int a, int b ){
    int set_a = find_ancestor( a );
    int set_b = find_ancestor( b );

    if( set_a == set_b )
        return;
    // 将重量小的集合拼接到重量大的集合上
    if( set_weights[set_a] >= set_weights[set_b] ){
        set_weights[set_a] += set_weights[set_b];
        // 更新重量小的集合的根的父亲
        parent[set_b] = set_a;
    }
    else{
        set_weights[set_b] += set_weights[set_a];
        parent[set_a] = set_b;
    }
}

int main(){
    init();
    merge_set( 3, 4 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 4, 9 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 8, 0 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 2, 3 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 5, 6 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 5, 9 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 7, 3 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 4, 8 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
    cout << endl;

    merge_set( 6, 1 );
    for( int i = 0; i <= 9; ++i )
        cout << parent[i] << " ";
}

运行结果:



应用:

一个很经典的物理模型, N * N 的格子,每个格子有两种状态vacant“空白”或者occupied“被占用”,网格能被过滤,当且仅当顶部和底部能被空白的格子链接。如下,蓝色的是“空白”,白色的是“占用”,则第一幅图是能过滤的,第二幅图是不能被过滤的。



现在知道vacant状态的格子在图中出现的概率 P* 能够影响到图能否被过滤,现在要求 P*。

P < P* ,几乎都不能被过滤,

P > P* ,几乎都能被过滤。

(这个问题乍一看和Union-Find没什么关系)

但可这么做:

1.将格子全部初始化为被占用

2.实现 make_site_vacant() 操作,用于将邻接的格子用 Union 操作联系在一起

3.让所有处于顶部和底部的格子变为vacant

4.再随机将其他的格子变为vacant,直到能够find( 顶部,底部 )

5.估算出P*