如何确定竞争对手网站,网站建设助手 西部数码,Wordpress与dw,wordpress底部广告Disjoint Sets意思是一系列没有重复元素的集合。一种常见的实现叫做#xff0c;Disjoint-set Forest可以以接近常数的时间复杂度查询元素所属集合#xff0c;用来确定两个元素是否同属一个集合等#xff0c;是效率最高的常见数据结构之一。
Wiki链接#xff1a;https://en…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链接中有详细的伪码可供参考。
应用思路
前文中提到的模拟城市类型的游戏地图的构造是基于格子的道路是由一些列格子连接而成是比较典型的独立集合。使用思路
每次创建道路格子将其添加到Set查找与该道路相邻的其它道路进行合并经过一系列上述操作后相连的道路都进入同一集合了有相同的root查找两个建筑的连通情况找到与建筑相邻的道路查询两个建筑的道路格子直接是否在同一集合即可得到连通性。
关于删除道路
删除一个道路找出与其相邻的所有道路格子将这些格子的parent设置为自身然后进行深度遍历合并集合。
