数据结构：DisjointSet

Disjoint Sets意思是一系列没有重复元素的集合。一种常见的实现叫做，Disjoint-set Forest可以以接近常数的时间复杂度查询元素所属集合，用来确定两个元素是否同属一个集合等，是效率最高的常见数据结构之一。

Wiki链接：https://en.wikipedia.org/wiki/Disjoint-set_data_structure

最近工作中制作一个模拟城市类型的游戏Demo，其中工业区和居民区之间需要有道路连通，两个区域才能发展，进行数值计算。使用Disjoint Set进行连通性测试，实现简单，性能绝佳。

结构实现

主要有三个操作：添加、合并、查询。用图形表示，数据结构大致逻辑为：

添加8个元素，他们分别在自己的集合中。

经过几次合并操作后，变成这样的集合状态。此时：1和2就在同一集合；1和7在不同集合。

表示

把每一个集合以一棵树表示，每一个节点即是一个元素。节点保存着到它的父节点的引用，树的根节点则保存一个空引用或者到自身的引用或者其他无效值，以表示自身为根节点。

添加

添加操作MakeSet(x)添加一个元素x，这个元素单独属于一个仅有它自己的集合。添加操作仅需将元素标记为根节点。

查询

在不交集森林中，每个集合的代表即是集合的根节点。查询操作Find(x)从x开始，根据节点到父节点的引用向根行进，直到找到根节点。

路径压缩优化

在集合很大或者树很不平衡时，上述代码的效率很差，最坏情况下（树退化成一条链时），单次查询的时间复杂度高达O(n)。一个常见的优化是路径压缩：

在查询时，把被查询的节点到根节点的路径上的所有节点的父节点设置为根结点，从而减小树的高度。也就是说，在向上查询的同时，把在路径上的每个节点都直接连接到根上，以后查询时就能直接查询到根节点。

合并

合并操作Union(x, y)把元素x所在的集合与元素y所在的集合合并为一个。合并操作首先找出节点x与节点y对应的两个根节点，如果两个根节点其实是同一个，则说明元素x与元素y已经位于同一个集合中，否则，则使其中一个根节点成为另一个的父节点。

按秩合并优化

上述代码的问题在于，可能会使得树不平衡，增大树的深度，从而增加查询的耗时。一个控制树的深度的办法是，在合并时，比较两棵树的大小，较大的一棵树的根节点成为合并后的树的根节点，较小的一棵树的根节点则成为前者的子节点。

判断树的大小有两种常用的方法，一个是以树中元素的数量作为树的大小，这被称为按大小合并。

另一种做法则是使用Rank来比较树的大小。Rank的定义如下：

• 只有根节点的树（即只有一个元素的集合），Rank为0；
• 当两棵Rank不同的树合并后，新的树的Rank为原来两棵树的Rank的较大者；
• 当两棵Rank相同的树合并后，新的树的Rank为原来的树的Rank加一。

容易发现，在没有路径压缩优化时，树的Rank等于树的深度减一。在有路径压缩优化时，树的Rank仍然能反映出树的深度和大小。在合并时根据两棵树的Rank的大小，决定新的根节点，这被称作按Rank合并。

Wiki链接中有详细的伪码，可供参考。

应用思路

前文中提到的模拟城市类型的游戏，地图的构造是基于格子的，道路是由一些列格子连接而成，是比较典型的独立集合。使用思路：

1. 每次创建道路格子，将其添加到Set；
2. 查找与该道路相邻的其它道路，进行合并；
3. 经过一系列上述操作后，相连的道路都进入同一集合了；有相同的root
4. 查找两个建筑的连通情况，找到与建筑相邻的道路，查询两个建筑的道路格子直接是否在同一集合，即可得到连通性。

关于删除道路

删除一个道路，找出与其相邻的所有道路格子，将这些格子的parent设置为自身，然后进行深度遍历合并集合。