当前位置:天才代写 > tutorial > 大数据教程 > 数据结构之并查集

数据结构之并查集

2021-03-04 12:47 星期四 所属: 大数据教程 浏览:30

1、  简述

并查集(Disjoint set或是Union-find set)是一种树形的算法设计,常见于解决一些不交叉结合(Disjoint Sets)的合拼及查看难题。

2、  操作过程

并查集是一种比较简单的算法设计,它关键涉及到2个操作过程,各自为:

A. 合拼2个不交叉结合

B. 分辨2个原素是不是归属于同一个结合

(1)       合拼2个不交叉结合(Union(x,y))

合拼实际操作非常简单:先设定一个二维数组Father[x],表明x的“爸爸”的序号。那麼,合拼2个不交叉结合的方式便是,寻找在其中一个结合最爸爸的爸爸(也就是最悠久的先祖),将此外一个结合的最悠久的先祖的爸爸偏向它。

图中为2个不交叉结合,b图为合拼后Father(b):=Father(g)

(2)       分辨2个原素是不是归属于同一结合(Find_Set(x))

本实际操作可变换为找寻2个原素的最悠久先祖是不是同样。能够选用递归完成。

3、  提升

(1)       Find_Set(x)时,途径缩小

找寻先祖时,大家一般选用递归搜索,可是当原素许多 亦或是整棵树变成一条链时,每一次Find_Set(x)全是O(n)的复杂性。为了更好地防止这类状况,大家需对途径开展缩小,即在我们历经”递推”寻找先祖连接点后,”回朔”的情况下顺带将它的子孙后代连接点都立即偏向先祖,那样之后再度Find_Set(x)时复杂性就变为O(1)了,如下图所显示。由此可见,途径缩小便捷了之后的搜索。

(2)       Union(x,y)时,按秩合拼

即合拼的情况下将原素少的结合合拼到原素多的结合中,那样合拼以后树的高宽比会相对性较小。

4、  程序编写完成

int father[MAX];   /* father[x]表明x的父节点 */
int rank[MAX];     /* rank[x]表明x的秩 */
/* 复位结合 */
void Make_Set(int x)
{
    father[x] = x; //父节点给自己(依据具体情况特定父节点可转变)
    rank[x] = 0;   //秩为0(依据具体情况复位秩还可以有一定的转变)
}
/* 搜索x原素所属的结合,回朔时缩小途径 */
int Find_Set(int x)
{
    if (x != father[x])
    {
        rank[father[x]]  = rank[x];
        //递归,以寻找最悠久先祖
        //回朔时缩小途径:途径上的全部子孙后代连接点都偏向最悠久先祖
        father[x] = Find_Set(father[x]);
    }
    return father[x];
}
/* 
   按秩合拼x和y所属的结合
   下边的那一个if else构造并不是肯定的,实际依据状况转变
   可是,服务宗旨是不会改变的即,按秩合拼,自动更新秩。
*/
void Union(int x, int y)
{
    x = Find_Set(x);  //寻找最悠久先祖
    y = Find_Set(y);
    if (x == y) return;  //2个原素归属于同一个结合
    if (rank[x] > rank[y])  //把深层小的结合合拼到深层大的结合中去
    {
        father[y] = x;
        rank[x]  = rank[y];  //升级合拼后的深层
    }
    else
    {
        if (rank[x] == rank[y])
        {
            rank[y]  ;
        }
        father[x] = y;
    }
}

5、  复杂性剖析

空间复杂度为O(N),创建一个结合的算法复杂度为O(1),N次合拼M搜索的算法复杂度为O(M Alpha(N)),这儿Alpha是Ackerman涵数的某一反函数,在非常大的范畴内(人们现阶段观察到的宇宙空间范畴估计有10的80三次方个分子,这低于前边常说的范畴)这一涵数的值能够当做是不超4的,因此并查集的实际操作能够当作是线形的。实际复杂性剖析全过程见参考文献(3)。

6、  运用

并查集常做为另一种繁杂的算法设计或是优化算法的存储结构。普遍的运用有:求无向图的连通分量数量,近期公共性先祖(LCA),带限定的工作排列,完成Kruskar优化算法求最小生成树等。

7、  参考文献

(1)       并查集:http://www.nocow.cn/index.php/并查集

(2)       博闻《并查集详解》:http://www.cnblogs.com/cherish_yimi/

(3)       Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498–524.

 

    关键字:

天才代写-代写联系方式