浦项建设内部网站,营销团队建设与管理,国外免费网站域名服务器查询软件,企业邮箱登录入口手机网页版一、场景
有时候我们会遇到这样的场景#xff0c;比如:M{1,4,6,8},N{2,4,5,7}#xff0c;我的需求就是判断{1,2}是否属于同一个集合#xff0c;当然实现方法有很多#xff0c;一般情况下#xff0c;普通青年会做出 O(MN)的复杂度#xff0c;那么有没有更轻量级的复杂度呢…一、场景
有时候我们会遇到这样的场景比如:M{1,4,6,8},N{2,4,5,7}我的需求就是判断{1,2}是否属于同一个集合当然实现方法有很多一般情况下普通青年会做出 O(MN)的复杂度那么有没有更轻量级的复杂度呢并查集就是用来解决这个问题的。
二、操作
从名字可以出来并查集其实只有两种操作并(Union)和查(Find)并查集是一种算法所以我们要给它选择一个好的数据结构通常我们用树来作为它的底层实现。
2.1、节点定义 #region 树节点/// summary/// 树节点/// /summarypublic class Node{/// summary/// 父节点/// /summarypublic char parent;/// summary/// 节点的秩/// /summarypublic int rank;}#endregion2.2、Union 操作
1 原始方案 首先我们会对集合的所有元素进行打散最后每个元素都是一个独根的树然后我们 Union 其中某两个元素让他们成为一个集合最坏情况下我们进行 M 次的 Union 时会存在这样的一个链表的场景。 从图中我们可以看到Union 时出现了最坏的情况而且这种情况还是比较容易出现的最终导致在 Find 的时候就相当复杂了为 O(N)。 2 按秩合并 我们发现出现这种情况的原因在于我们 Union 时都是将合并后的大树作为小树的孩子节点存在那么我们在 Union 时能不能判断一下将小树作为大树的孩子节点存在最终也就降低了新树的深度比如图中的 Union(D,{E,F})的时候可以做出如下修改。 可以看出我们有效的降低了树的深度在 N 个元素的集合中构建树的深度不会超过 LogN 层。M 次操作的复杂度为 O(MlogN)从代码上来说我们用 Rank 来统计树的秩可以理解为树的高度独根树时 Rank0当两棵树的 Rank 相同时可以随意挑选合并在新根中的 Rank 就可以了。 #region 合并两个不相交集合/// summary/// 合并两个不相交集合/// /summary/// param nameroot1/param/// param nameroot2/param/// returns/returnspublic void Union(char root1, char root2){char x1 Find(root1);char y1 Find(root2);//如果根节点相同则说明是同一个集合if (x1 y1)return;//说明左集合的深度 右集合if (dic[x1].rank dic[y1].rank){//将左集合指向右集合dic[x1].parent y1;}else{//如果 秩 相等则将 y1 并入到 x1 中并将x1if (dic[x1].rank dic[y1].rank)dic[x1].rank;dic[y1].parent x1;}}#endregion2.3、Find 操作
我们学算法都希望能把一个问题优化到不能优化的地步针对 logN 的级别我们还能优化吗当然可以。 1 路径压缩 在 Union 和 Find 这两种操作中显然我们在 Union 上面已经做到了极致下面我们在 Find 上面考虑一下是不是可以在 Find 上运用伸展树的思想这种伸展思想就是压缩路径。 从图中我们可以看出当我 Find(F)的时候找到“F”后我们开始一直回溯在回溯的过程中给把该节点的父亲指向根节点。最终我们会形成一个压缩后的树当我们再次 Find(F)的时候只要 O(1)的时间就可以获取这里有个注意的地方就是 Rank当我们在路径压缩时最后树的高度可能会降低可能你会意识到原先的 Rank 就需要修改了所以我要说的就是当路径压缩时Rank 保存的就是树高度的上界而不仅仅是明确的树高度可以理解成伸缩椅伸时候的长度。 #region 查找x所属的集合/// summary/// 查找x所属的集合/// /summary/// param namex/param/// returns/returnspublic char Find(char x){//如果相等则说明已经到根节点了返回根节点元素if (dic[x].parent x)return x;//路径压缩(回溯的时候赋值最终的值就是上面返回的x也就是一条路径上全部被修改了)return dic[x].parent Find(dic[x].parent);}#endregion我们注意到在路径压缩后我们将 LogN 的复杂度降低到 Alpha(N)Alpha(N)可以理解成一个比 hash 函数还有小的常量这就是算法的魅力。
