首页 > 数据结构 > 并查集 > 并查集(2)-按秩合并和路径压缩
2014
03-20

并查集(2)-按秩合并和路径压缩

在上面一讲是并查集(1)-判断无向图是否存在环. 我们使用了并查集的两个操作: union() 和 find()

//  find 的原始实现
int find(int parent[], int i)
{
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

// union()的原始实现
void Union(int parent[], int x, int y)
{
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

上述union()和find()是直接的,最坏的情况下的时间复杂度是线性的。表示子集的树可能会倾斜,像一个链表。下面是一个例子最坏情况的场景。

假设有4个元素 0, 1, 2, 3
初始化
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
     2   3   
    /
   1
 /
0

Do Union(2, 3)
         3    
        /
      2
     /
   1
 /
0

以上操作可以优化到O(Log n)在最糟糕的情况下。方法就是在每次合并都把深度较小的集合合并在深度较大的集合下面 。这种技术被称为按秩合并。这样可以防止树的退化,最坏情况不会出现。

继续用上面的例子
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
    1    
 /  |  \
0   2   3

第二个要优化的就是find(). 路径压缩实际上是在找完根结点之后,在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。

假设集合{0, 1, .. 9} 的树表示如下所示:  当调用 find(3)时

              9
         /    |    \  
        4     5      6
     /     \        /  \
    0        3     7    8
            /  \
           1    2  

我们向上查找,找到是这个集合的根节点. 路径压缩就是:直接把 3的 父节点 设置为 9
当下次再查找 1, 2 或 3 时,查找的路径就会变短。

               9
         /    /  \    \
        4    5    6     3 
     /           /  \   /  \
    0           7    8  1   2

这两个优化方法互为补充。每个操作的时间复杂度比O(Logn)要小。事实上,摊销时间复杂度实际上变成了小的常数。

// 用并查集判断是否存在环
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 图中的边
struct Edge
{
    int src, dest;
};

// 图结构体
struct Graph
{
    // V-> 顶点个数, E-> 边的个数
    int V, E;

    // 每个图就是 边的集合
    struct Edge* edge;
};

struct subset
{
    int parent;
    int rank;
};

// 创建一个图
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

    return graph;
}

// 使用路径压缩
int find(struct subset subsets[], int i)
{
    // 找到 root并使  root 作为 i 的父节点 
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);

    return subsets[i].parent;
}

// 使用按秩合并
void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    // 将深度较小的集合 合并到深度大的集合下面
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else //深度一样,任选一个,并增加另一个
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++; 
    }
}

int isCycle( struct Graph* graph )
{
    int V = graph->V;
    int E = graph->E;

    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );

    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    for(int e = 0; e < E; ++e)
    {
        int x = find(subsets, graph->edge[e].src);
        int y = find(subsets, graph->edge[e].dest);

        if (x == y)
            return 1;

        Union(subsets, x, y);
    }
    return 0;
}

// Driver program to test above functions
int main()
{
    /* 构造以下的图
         0
        |  \
        |    \
        1-----2 */

    int V = 3, E = 3;
    struct Graph* graph = createGraph(V, E);

    // add edge 0-1
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;

    // add edge 1-2
    graph->edge[1].src = 1;
    graph->edge[1].dest = 2;

    // add edge 0-2
    graph->edge[2].src = 0;
    graph->edge[2].dest = 2;

    if (isCycle(graph))
        printf( "Graph contains cycle" );
    else
        printf( "Graph doesn't contain cycle" );

    return 0;
}

参考:http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }