黑马程序员技术交流社区

标题: [算法学习]并查集入门实例精讲 [打印本页]

---

作者: ciying88    时间: 2017-3-10 00:20
标题: [算法学习]并查集入门实例精讲

一、什么是并查集

    并查集：即不相交集合。一种简单的用途广泛的集合，实现了较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar算法求最小生成树。

并查集实现方法：
    每个集合用一棵“有根树”表示；
    定义数组  int[] father
              int[] rank  
    father=i,则i表示本集合且i是集合对应的树的根
    father=j,则表示j是i的父节点

    rank代表集合i的秩(比如子孙的多少或树的高度等），用于合并集合，秩小的合并到秩大的。   
  
   
   

     
   

     
   
  



二、并查集的精髓（即它的三种操作）：


1、Make_Set() 把每一个元素初始化为一个集合

     初始化后每一个元素的父亲节点是它本身。



     void Make_Set() {

      for(int i=0;i<father.length;i++){

        father = i; //根据实际情况指定的父节点可变化

        rank = 0; //根据实际情况初始化秩也有所变化

      }  

   }




2、Find_Set(x) 查找一个元素所在的集合

    查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！

    判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。

    合并两个集合，也是使一个集合的祖先成为另一个集合的祖先



   //递归实现找祖先

   int Find_Set(int x){

     if (x != father[x]){

      father[x] = Find_Set(father[x]);//这个回溯时的压缩路径是精华,将查找路径的所有节点都指向根节点

     }

     return father[x];

    }





   //循环实现找祖先



   int Find_Set(int x)

{

     int root=x;

     while(father[root]!=root)

         root=father[root];

     return root;

   }



    //循环实现找祖先，路径压缩

    //每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快

    //第一步，找到根节点；第二步，修改查找路径上的所有节点，将它们都指向根结点

    int Find_Set(int x){

      int k,root;

      root=x;

      while(root!=bin[root])  //循环找x的根      

          root=father[root];

      while(x!=root)//本循环修改查找路径中的所有节点使其指向根节点---压缩

      {

          k=father[x];

          father[x]=root;//指向根节点

          x=k;

      }

      return x;

     }



路径压缩示意图：









3、Union(x,y) 合并x,y所在的两个集合

   合并两个不相交集合操作很简单：

   利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。



void Union(int x, int y){//合并集合的条件要试具体问题而定,这里将秩小的合并到秩大的。

     x = Find_Set(x);

     y = Find_Set(y);

     if (x == y) return;

     if (rank[x] > rank[y]) {   

             father[y] = x;   

      } else if (rank[x] < rank[y]) {   

             father[x] = y;   

      } else {   

             rank[y]++;   

             father[x] =y;   

      }   



}




三、并查集的优化

1、Find_Set(x)时路径压缩

    寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Set(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？

答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，

这样以后再次Find_Set(x)时复杂度就变成O(1)了。



2、Union(x,y)时按秩合并

即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。






实例一：判断亲戚关系.

    若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。



规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。



     先输入10个人（编号从1-10）及7组亲戚关系，然后输入3组数据，问这三组数据是不是亲戚关系？



输入

10 7

2 4

5 7

1 3

8 9

1 2

5 6

2 3

3

3 4

7 10

8 9



输出

Yes

No

Yes



分析：其实本题只是一个对分离集合（并查集）操作的问题。我们可以给每个人建立一个集合，集合的元素值有他自己，表示最开始时他不知道任何人是它的亲戚。以后每次给出一个亲戚关系a, b，则a和他的亲戚与b和他的亲戚就互为亲戚了，将a所在集合与b所在集合合并。



     最后我们得到3个集合{1,2,3,4}, {5,6,7}, {8,9}，于是判断两个人是否亲戚的问题就变成判断两个数是否在同一个集合中的问题。


import java.util.Scanner;
   public class Main{
     int[] father;
     int[] rank;
    public Main(){
       }

    public void go(){
      Scanner in=new Scanner(System.in);
       int n=in.nextInt();
       int m=in.nextInt();
       father=new int[n+1];
       rank=new int[n+1];
        Make_Set();
       for(int i=1;i<=m;i++){
           int a=in.nextInt();
           int b=in.nextInt();
           int x=Find_Set(a);
           int y=Find_Set(b);
           Union(x,y);
       }
       //for(int i=1;i<=n;i++)
       //  System.out.print("father["+i+"]="+father+"  ");
       int k=in.nextInt();
       for(int i=1;i<=k;i++){
           int x=in.nextInt();
           int y=in.nextInt();
           if(Find_Set(x)==Find_Set(y)) System.out.println("Yes");
           else  System.out.println("No");
       }
     }
   
      
    private void Make_Set() {
     for(int i=0;i<father.length;i++){
       father = i; //根据实际情况指定的父节点可变化
       rank = 0; //根据实际情况初始化秩也有所变化
     }  
    }
  
    private int Find_Set(int x){
     if (x != father[x]){
       father[x] = Find_Set(father[x]);//这个回溯时的压缩路径是精华,将查找路径的所有节点都指向根节点
      }
     return father[x];
    }
    void Union(int x, int y){
      int f1 = Find_Set(x);
      int f2 = Find_Set(y);
       if(f1!=f2) father[f1]=f2;
   
    }
  
     public static void main(String args[]){
        Main m=new Main();
        m.go();
     }
  }[/code]

---

作者: 雪飞舞舞    时间: 2017-3-10 17:53
看看。。。。。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2