并查集

来自计算思维百科
跳转至: 导航搜索
并查集.png

小明很喜欢养花,他养了各种各样的花,有多年生的,有一年生的,有开花的,有观叶的,不同类型的花有不同的品种。那么,怎么样把小明养的花用一个数据类型表达呢?并查集就是完成这个功能的一种抽象数据类型,它能把数据划分为不相交的子集合,例如,茶花分成一个子集,这个集合中有多个品种的茶花,如十八学士、大紫袍、状元红等;而多肉植物又分成一个子集,包括玉露、观音莲、宝石花等等。在这些集合中可以进行合并和查询的操作,例如多肉植物和绿叶植物可以合并成一个观叶植物的集合,在多肉植物的集合中可以查询观音莲等等。能够完成这些操作的抽象数据类型就是并查集。

基本概念

在许多地方都有遇到过需要把一个含n个元素的集合划分成一系列不相交子集的情况。在我们把它们初始化成n个单元素集合后,我们可以对这些集合做一系列求并集和查找的混合操作。这个过程涉及到的集合和操作我们抽象成一种数据类型,就叫做并查集。

应用范围

并查集被广泛应用与图问题有关的解决过程中,也可以用来对数据进行分类。

使用方法及步骤

  1. 将n个元素生成n个单元素集合;
  2. 利用操作find(x)返回元素x所在的集合;
  3. 利用Union(x, y)将含x和含y的不相交子集合并删除原来的两个集合。

应用案例

应用1-关系追踪

案例:若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。规定:若a和b是亲戚,b和c是亲戚,那么a和c也是亲戚。假设有200个人。

解决步骤:在前面的算法中我们也有提到过利用图来追踪关系,但当规模较大时,用图来解决显然是极复杂的,这里我们通过并查集的方法可以有效优化解决效率。我们把有亲戚关系的人看 做一个集合,问题就转化为判断两个元素是否在同一集合。

  1. 每个人各自属于自己的一个集合。即初始有200个集合,每个集合里有一个人。
  2. 若a和b有关系,则先找到a、b所在集合;
  3. 合并集合,重复23直到没有新的关系出现;
  4. 此时,若要判断任意两人是否为亲戚,只需利用find(x)函数来查询两个元素是否在同一集合即可,若是,则为亲戚,不是则不是亲戚。

应用2-计算团伙数目

案例:在某个城市里住着n个人,任何两个认识的人不是朋友就是敌人,而且满足:我朋友的朋友就是我的朋友;已知关于n个人的m条信息(即2个人是朋友还是敌人),假设所有是朋友的人一定属于一个团伙,请计算该城市有多少个团伙?

解决步骤:类似于上面的案例,我们也可以利用并查集的方法,将是朋友关系的人放在一个集合,属于不同集合的就是敌人,则这个问题就转化成了求最后的不相交集合有多少个。

  1. 每个人各自属于自己的一个集合。每个集合里有一个人。
  2. 对于任意两个人a、b,则先找到a、b所在集合;
  3. 若a、b是朋友则合并两者集合,若两者是敌人则不合并。重复23直到没有新的关系出现;
  4. 此时,集合的个数即为团伙的个数。

可以体现的计算思维

并查集是一种抽象的数据类型,可以将相似的数据归为一类,并进行合并和查找操作,体现了计算思维的抽象特点。