MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 简略并查集归纳

简略并查集归纳

www.MyException.Cn  网友分享于:2013-11-02  浏览:0次
简单并查集归纳

并查集就是一种一边查找一边并集的数据结构,简单的并查集经常应用于朋友圈等题目,即:x和y是朋友,y和z是朋友,则x和z是朋友,下面给出一组数据表示xx和yy是朋友,最后问一共有多少个朋友圈。这类问题一般用并查集解决比较快。
下面明确并查集做的事情:
1.查集,即查找某个元素是否包含在一个集合里面
2.并集,即将两个集合合并到一块
知道并查集要做的事后,实现它就比较简单了,数据结构书上教我们的是用树的方法来实现并查集,即用一个数组来模拟树,然后利用树的特性来实现,但是那个一下子会有点难以理解,所以我们一开始可以用java自带的集合类来模拟实现,帮助理解。
下面是用java集合来实现并查集的代码:

 1 import java.io.*;
 2 import java.util.*;
 3 
 4 public class javaSet_union_find_set {
 5     static int n;
 6     static List<Set<Integer>>list = new ArrayList<Set<Integer>>();
 7     public static void main(String[] args){
 8         Scanner in = new Scanner(new BufferedInputStream(System.in));
 9         n = in.nextInt();
10         //初始化,为每个人单独建立一个集合
11         for(int i=1;i<=n;i++){
12             Set<Integer>set = new HashSet<Integer>();
13             set.add(i);
14             list.add(set);
15         }
16         int m = in.nextInt();
17         for(int i=0;i<m;i++){
18             int x = in.nextInt();
19             int y = in.nextInt();
20             union(x,y);
21         }
22         for(int i=0;i<list.size();i++){
23             System.out.println("集合"+i+":");
24             System.out.print("( ");
25             for(int number:list.get(i)){
26                 System.out.print(number+" ");
27             }
28             System.out.print(")\n");
29         }
30         System.out.println(list.size());
31     }
32     //查集操作,返回一个集合,即元素所在的集合
33     public static Set<Integer> find(int x){
34         for(Set set:list){
35             if(set.contains(x)){
36                 return set;
37             }
38         }
39         return null;
40     }
41     //并集操作,将两个元素所在的集合合并
42     public static void union(int a,int b){
43         Set<Integer>set1 = find(a);
44         Set<Integer>set2 = find(b);
45         //当两个集合不相等的时候,合并他们
46         if(set1!=set2){
47             list.remove(set1);
48             list.remove(set2);
49             set1.addAll(set2);
50             list.add(set1);
51         }
52     }
53 }

 

所用到的思想就是简单并查集的思想,下面我们假设一组数据来具体说明,
测试数据:
6 4
1 2
1 3
1 4
5 6
第一行第一个数为n,即一共有多少个人,第二个数为m,即以下给出m对关系,接着m行,每行两个数,表示第x个人和第y个人是朋友关系
答案:
2
最后应该是,1,2,3,4是一组朋友关系,5,6是一组朋友关系,故一共有两个朋友圈
用并查集来解决这个问题,就是要运用集合的特性,即两个集合有并集操作。
故,我们一开始给每一个人创建一个集合,即每个人都是单独的一个集合,下面给出初始关系,用()表示一个集合。
初始关系为:(1),(2),(3),(4),(5),(6)
对m行数据进行处理:
1和2是朋友,那么包含1的集合和包含2的集合合并,则现在关系为:
(1,2),(3),(4),(5),(6)
1和3是朋友,并集后:
(1,2,3),(4),(5),(6)
1和4是朋友,并集后:
(1,2,3,4),(5),(6)
5和6是朋友,并集后:
(1,2,3,4),(5,6)
这就是完整的一次集合操作,最后数组list的长度即为朋友圈的个数

上面用java的集合类Set模拟了一下并查集的具体操作,每次查集的时间复杂度为数组的长度即O(N),每次并集的复杂度为原本java集合类并集的复杂度,有m次查询,粗略计算时间复杂度为O(mn),即O(N),也算是线性复杂度吧。
接下来是传统做法,用数组模拟树来实现,用数组模拟树实现并查集如下所示:

一开始每个人都是独立的集合
(1),(2),(3),(4),(5),(6)
1和2是朋友,并集后:
(1),(3),(4),(5),(6)
 |
(2)
1和3是朋友,并集后:
(1)  ,(4),(5),(6)
 | \
(2) (3)
1和4是朋友,并集后:
  (1) ,(5),(6)
 / | \
(4)(2)(3)
5和6是朋友,并集后:
  (1) ,    (5)
 / | \      |
(4)(2)(3)  (6)

 


上面只是模拟了并查集操作,具体的指向为具体的程序的启发函数决定。
使用数组模拟树的并查集有以下几点需要注意:
1.路径压缩操作,在并集操作中很可能出现下面这个情况:

    (1)       (5)
     |         |
    (2)       (6)
     |
    (3)
     |
    (4)

 


当出现这种树的时候,进行查集操作的时候会额外消耗更多的查询时间。
所以这时要运用路径压缩的方法,即每次进行查询操作的时候都进行路径压缩,即查询子节点的时候,都将子节点指向根节点
2.并集操作中怎么合并两个集合,应该根据什么来进行合并
这里有两个启发函数可以选择:
1.根据节点数量进行合并,即将节点少的树结合到节点数量多的树中
2.根据树的高度进行合并,即将高度小的树合并到高度高的树
下面两个启发函数分别举例,先是使用启发函数1+路径压缩的做法,代码如下:

 1 import java.io.*;
 2 import java.util.*;
 3 
 4 public class union_find_set {
 5     //父节点数组,father[x]=y表示x的父节点为y
 6     //如果father[x]小于0,则说明x是一个根节点,此时father[x]的绝对值是
 7     //这颗树的节点数量
 8     static int[] father;
 9     static int n;
10     public static void main(String[] args){
11         Scanner in = new Scanner(new BufferedInputStream(System.in));
12         n = in.nextInt();
13         int m = in.nextInt();
14         father = new int[n+1];
15         //初始化父节点数组
16         for(int i=0;i<=n;i++){
17             father[i] = -1;
18         }
19         for(int i=0;i<m;i++){
20             int x = in.nextInt();
21             int y = in.nextInt();
22             union(x,y);
23         }
24         for(int i=1;i<=n;i++){
25             System.out.println("find("+i+"):"+find(i));
26         }
27     }
28     //查集操作,查找x元素所属的集合的根节点,同时进行路径压缩操作
29     public static int find(int x){
30         int root = x;
31         while(root>=0){
32             root = father[root];
33         }
34         //此时已找到根节点为root
35         
36         //路径压缩
37         while(x!=root){
38             int temp = x;
39             x = father[x];    //x继续往上一个父节点追溯,直到根节点
40             father[temp] = root;    //路径压缩,把所有子节点都直接指向根节点
41         }
42         
43         return root;
44     }
45     //并集操作,将两个集合合并,将x元素所属的集合和y元素所属的集合合并
46     public static void union(int x,int y){
47         int fx = find(x);
48         int fy = find(y);
49         //temp的绝对值为两棵树的节点数量总和
50         int temp = fx + fy;
51         //说明x元素所属的集合节点比y元素所属的集合少
52         //那么将节点少的集合合并到节点多的集合上
53         if(fx>fy){
54             father[x] = y;
55             father[y] = temp;
56         }else{
57             father[x] = temp;
58             father[y] = x;
59         }
60     }
61 }

 

使用启发函数1的做法,那么模拟树的数组有一点要注意的就是,为负数的时候表示这是一个根节点,并且此负数的相反数为该棵树的节点总数
一下是使用启发函数2的做法,代码如下:

 1 import java.io.*;
 2 import java.util.*;
 3 
 4 //使用启发函数2的做法
 5 public class union_find_set_another {
 6     static int[] father;    //记录每个节点的父节点,father[x]=y表示为x元素的父节点为y元素
 7     static int[] rank;        //记录每棵树的高度,rank[x]=h表示为x元素所含集合的深度为h
 8     static int n;
 9     public static void main(String[] args){
10         Scanner in = new Scanner(new BufferedInputStream(System.in));
11         n = in.nextInt();
12         father = new int[n+1];
13         rank = new int[n+1];
14         int m = in.nextInt();
15         //初始化father数组
16         //令每个节点一开始都指向自己
17         for(int i=0;i<=n;i++){
18             father[i] = i;
19         }
20         //初始化rank数组
21         for(int i=0;i<=n;i++){
22             rank[i] = 1;
23         }
24         for(int i=0;i<m;i++){
25             int x = in.nextInt();
26             int y = in.nextInt();
27             union(x,y);
28         }
29         for(int i=1;i<=n;i++){
30             System.out.println("find("+i+"):"+find(i));
31         }
32     }
33     public static int find(int x){
34         if(x!=father[x]){
35             return find(father[x]);
36         }
37         return x;
38     }
39     public static void union(int x,int y){
40         int fx = find(x);
41         int fy = find(y);
42         if(fx==fy){
43             //说明两个元素同属一个集合,这种情况直接返回
44             return;
45         }
46         //此处应用启发函数2,根据树的高度来进行合并
47         //这里我们将高度小的合并到高度大的树上
48         if(rank[fx]>rank[fy]){
49             father[fy] = fx;
50         }else{
51             if(rank[fx]==rank[fy]){
52                 //当两棵树一样高的时候,则增加其中一棵的高度
53                 rank[fy]++;
54             }
55             father[fx] = fy;
56         }
57     }
58 }

 

启发函数2中额外使用了一个rank数组来记录树的高度,并让father数组严格遵守father[x]=y表示x的父节点为y这一个规定,使用find函数查找根节点会返回根节点的值,而不是节点数量,这一点比启发函数1来的好用,再加上代码短,思路清晰这一点,我是建议都用启发函数2来实现的>.<
简单并查集的归纳就到这里了,如果想验证代码的正确性的话,下面有几个题目可以选择:
https://leetcode.com/problems/friend-circles/description/   leetcode的朋友圈问题,经典的并查集应用
http://codevs.cn/problem/2597/   团伙问题,敌人的敌人是朋友是需要注意的一点

最后说几句,这篇文章是我从《算法竞赛宝典》数据结构一章归纳总结而来,如果有什么问题或纰漏,请您指出,本人感激不尽~~~

文章评论

10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员必看的十大电影
程序员必看的十大电影
那些争议最大的编程观点
那些争议最大的编程观点
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
10个调试和排错的小建议
10个调试和排错的小建议
老程序员的下场
老程序员的下场
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员都该阅读的书
程序员都该阅读的书
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
每天工作4小时的程序员
每天工作4小时的程序员
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
旅行,写作,编程
旅行,写作,编程
 程序员的样子
程序员的样子
编程语言是女人
编程语言是女人
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
代码女神横空出世
代码女神横空出世
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
为什么程序员都是夜猫子
为什么程序员都是夜猫子
鲜为人知的编程真相
鲜为人知的编程真相
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
Java程序员必看电影
Java程序员必看电影
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
如何成为一名黑客
如何成为一名黑客
漫画:程序员的工作
漫画:程序员的工作
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
中美印日四国程序员比较
中美印日四国程序员比较
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
我的丈夫是个程序员
我的丈夫是个程序员
程序员的鄙视链
程序员的鄙视链
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员应该关注的一些事儿
程序员应该关注的一些事儿
总结2014中国互联网十大段子
总结2014中国互联网十大段子
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
一个程序员的时间管理
一个程序员的时间管理
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有