新网站改关键词,开发公司购买的游乐设备计入什么科目,海口自助建站,asp.net 窗体网站引入
那么我们在介绍我们并查集的原理之前#xff0c;我们先来看一下并查集所应用的一个场景#xff1a;那么现在我们有一个长度为n的数组#xff0c;他们分别属于不同的集合#xff0c;那么现在我们要查询数组当中某个元素和其他元素是否处于同一集合当中#xff0c;或者…
引入
那么我们在介绍我们并查集的原理之前我们先来看一下并查集所应用的一个场景那么现在我们有一个长度为n的数组他们分别属于不同的集合那么现在我们要查询数组当中某个元素和其他元素是否处于同一集合当中或者我们想把它们合并到同一个集合当中以及查询该集合的数量那么这些都可以交给我们的并查集来进行实现。
那么我们数组中处于相同的集合的元素的位置是离散的那么很多人看到并查集所应用的场景那么常规思路实现我们的并查集一般会想到就是采取我们的哈希表这个数据结构对于每一个集合我们建立一张哈希表如果我们查询这两个元素是否在同一个集合当中那么我们就是确定他们是否在同一张表当中那么就会遍历我们这张哈希表如果要合并两个不同的集合那么我们就该另一张哈希表中的元素全部添加进该哈希表当中我们哈希表实现我们的并查集是肯定没有问题的但是我们有更为简单并且高效的实现方式那么就是通过我们的数组来实现 并查集原理
那么我们首先我们知道我们判断两个元素所处的集合是否是一个集合那么我们的集合肯定得有一个标识符来进行区分那么这里我们区分不同的集合的话我们就是选取该集合当中的一个代表元素的索引或者编号来作为该集合的一个标识符。
那么我们会首先准备一个father数组和一个size数组(其中size数组可有可不有那么我们的father数组的每一个位置就对应我们原始数组当中的每一个位置那么其中father数组的作用就是确定数组每一个位置在集合当中的直接后继的节点编号是谁那么想你可能看不懂我刚才的那句话但是没关系我在下文会进行讲解。 那么我们首先初始化我们的并查集的时候我们将我们该数组中的每个元素自己作为一个集合那么该集合的代表元素就是他们本身
那么我们如何理解我们这个集合呢那么我们对于每一个集合来说那么处于该集合当中的元素就是以一个树的形式来进行组织的那么我们该树的根节点就是该集合的代表元素这个树不是说我们的并查集的集合的实现就是按照真的数据结构当中的树那样用指针进行构造而是说我们的处于同一集合当中的元素可以形象理解为他们是以一个树的形式来组织就像我们理解DFS的递归过程就形象的理解为类似于一棵多叉树的遍历。
那么最开始我们初始化并查集的时候假设我们现在有一个长度为n的数组那么我们先让该数组当中的每一个元素自己作为一个集合那么我们就可以理解为每个集合当中所对应对应的树的节点就只有一个就是当前数组每个元素它本身那么它的下一个直接后继节点就是它自己。
那么我们该数组中任意两个位置所处的集合要进行合并的话那么我们就首先判断他们是否处于同一个集合如果处于同一个集合就没有必要进行合并如果不处于同一个集合的话那么我们就可以合并那么刚开始我们每一个集合都只有当前数组每一个位置本身的一个元素那么我们合并的话我们就将我们这个其中一个集合所对应的树的根结点原本就是自己本身并且它的指向后继节点的指针是指向自己那么我们就该根结点的指针给指向另一个元素所处集合所对应树的根结点那么我们实现这个过程的话我们知道我们father数组记录的是数组当中每一个位置它的父节点的索引编号那么最开始由于我们每一个元素自己作为一个集合那么father数组当中的每一个位置的记录的父节点的编号就是他们本身 例father[0]0,father[1]1,father[2]2…
那么如果此时我们假设数组下标为0的元素与数组下标为1的元素合并了那么我们就在father数组当中下标为0的位置处原本记录的编号就是0那么我们将其修改为1那么此时这步操作我们就可以理解为我们一个集合对应的树的根节点的指针原本的指向是自己而现在我们在该集合所对应的树插入到另一个集合所对应的树当中作为一个子树了而我们该集合的根节点原本的指向是自己现在我们将其修改指向为另一个要合并集合对应的树的根节点所以此时该树的根节点不再是原先集合的根节点了而是另一个我们插入的集合原本的根节点所以现在两个集合的根节点相同那么两个集合就是同一个集合了从而实现合并。
那么接下来我们每次合并两个数组中任意两个数所处的集合我们都要先查找两个数所处的集合的代表元素的编号看他们是否相同而现在假设这个数组中的每个集合已经经过多次的合并那么意味着该元素所处的树上的节点可能不只有之前初始化时它自己一个了那么我们就得往上找到该元素所处的树的根结点那么我们知道father数组记录的是数组中每一个位置的元素在树当中的直接后继也就是它的父节点那么接下来我们就需要遍历我们的father数组假设我们现在要找下标为0的元素所处集合的根结点也就是代表元素那么我们就遍历father数组那么我们先找到father数组下标为0的元素值也就是下标为0的节点在树中的直接后继节点也就是父节点的编号假设为1那么接下来我们就到father数组下标为1位置处查看它所记录的编号为1的直接后继节点的编号是谁然后再对应跳转到该father数组的编号位置处而我们的根结点的直接后继我们在初始化设置的时候就是它自己所以如果我们发现father数组下标为3的记录的直接后继编号就是3那么3就是当前的下标为0的元素所处集合的代表元素。 那么我们知道了我们查询以及合并的一个原理之后那么我们就可以写我们并查集最为关键的两个函数find函数和union函数那么在给处这两个板子之前我们还能对并查集的进行两个优化
小挂大
那么我们除了我们的father数组那么我们还可以有我们的size数组那么size数组的每个位置和father数组一样对应原数数组当中的每一个位置我们size数组的作用则是记录我们每一个集合的元素个数那么我们要查找数组下标i位置所处的集合的元素个数那么我们就需要调用find函数找到我们下标为i位置的代表元素的下标q那么我们查询size[q]就可以查到i所处集合中的元素了那么所谓的小挂大就是我们知道我们合并两个不同的集合我们是将其中的一个集合所对应的树给插入到另一个集合对应的树中作为子树让该集合的树的根节点的指向修改指向另一个树的根节点来达到
但是我们对于并查集当中的操作真正影响时间复杂度的其实是我们的find操作因为我们每一次union操作前都要先find来确定完两个集合不相同后那么我们只需要将该集合根节点所对应的father数组修改为另一个集合的father数组的值而数组由于随机访问那么这步修改代价的时间复杂度是o(1),而我们find从当前下标为i的元素在树中往上遍历访问到根节点的时间复杂度则是o(n),所以我们优化时间性能就是尽可能让元素少的集合去插入到元素大的集合中去那么这样往上遍历的节点个数就相比于大挂小的节点个数要小所以遍历代价就会减小这就是我们的小挂大的优化
路径压缩
而路径压缩的方式是我们这两个优化中最高效的那么我们掌握了路径压缩我们甚至都不需要来小挂大来额外建立一个size数组但是为了让我们对并查集的理解更全面我还是介绍了小挂大的策略
那么我们的路径压缩就是我们当我们执行find操作的时候去查询该位置所处集合当中的根节点的时候我们会沿途往上遍历直到达到根节点那么我们这里在沿途往上遍历的过程中我们将我们沿途的每一个节点直接修改连接到根节点那么这样我们每一次find的时候我们该节点往上遍历就直接是根节点从而直接得到代表元素那么每次查询的时间复杂度就可以优化到O(1)!但是我们路径压缩的过程会有一个o(N)的代价但是一旦压缩之后之后的find都是常数时间复杂度了那么这个路径压缩优化下并查集的具体时间复杂度是专门有数学学家花了几十年时间来证明那么感兴趣的话可以下去自己去了解那么这里我就不在赘述了
而具体我们怎么将我们的沿途的各个节点直接连接根节点那么我们就通过栈或者递归来实现其中递归的实现原理就是我们的从当前该节点先递归找到根节点然后回溯到我们当前节点时会依次返回我们根节点的节点编号然后从而修改沿途节点的father数组的值。
find函数递归版本代码板子
int find(vectorint father,int x)
{if(x!father[x]){father[x]find(father[x]);}return father[x];
}union函数代码板子
void _union(vectorint father,int x,int y)
{int fxfind(father,x);int fyfind(father,y);if(fx!fy){father[fx]fy;}return;
}初始化father数组
vectorint father(nums.size()); // 创建一个与nums数组大小相同的father数组
for (int i 0; i father.size(); i) {father[i] i; // 将father数组的每个元素初始化为它自己的索引
}结语
那么这就是本篇并查集的全部内容本篇文章就介绍了并查集的原理以及实现那么相比于之前我的算法文章我还会引入几个与该算法相关的题目来应用但是由于博主最近有点忙所以就打算将我们的并查集算法篇分为两期一期讲原理另一期讲题所以这篇文章相比于我们之前的文章来说字数就较少那么我下一期我将会讲并查集的相关题目我会持续更新希望你多多关注那么如果本篇文章有帮助到你的话还请多多三连关注支持一下博主哦你的支持就是我最大的动力 文章转载自： http://www.morning.xkjqg.cn.gov.cn.xkjqg.cn http://www.morning.qfrsm.cn.gov.cn.qfrsm.cn http://www.morning.zylzk.cn.gov.cn.zylzk.cn http://www.morning.zgdnd.cn.gov.cn.zgdnd.cn http://www.morning.wkpfm.cn.gov.cn.wkpfm.cn http://www.morning.jsrnf.cn.gov.cn.jsrnf.cn http://www.morning.jhfkr.cn.gov.cn.jhfkr.cn http://www.morning.tnqk.cn.gov.cn.tnqk.cn http://www.morning.nqmhf.cn.gov.cn.nqmhf.cn http://www.morning.ksggl.cn.gov.cn.ksggl.cn http://www.morning.czwed.com.gov.cn.czwed.com http://www.morning.bswxt.cn.gov.cn.bswxt.cn http://www.morning.gqjzp.cn.gov.cn.gqjzp.cn http://www.morning.kqrql.cn.gov.cn.kqrql.cn http://www.morning.kyflr.cn.gov.cn.kyflr.cn http://www.morning.ykqbs.cn.gov.cn.ykqbs.cn http://www.morning.dpbdq.cn.gov.cn.dpbdq.cn http://www.morning.hnrdtz.com.gov.cn.hnrdtz.com http://www.morning.wdshp.cn.gov.cn.wdshp.cn http://www.morning.gctgc.cn.gov.cn.gctgc.cn http://www.morning.ssjee.cn.gov.cn.ssjee.cn http://www.morning.zcwwb.cn.gov.cn.zcwwb.cn http://www.morning.kqzt.cn.gov.cn.kqzt.cn http://www.morning.zgnng.cn.gov.cn.zgnng.cn http://www.morning.lbhck.cn.gov.cn.lbhck.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.qkpzq.cn.gov.cn.qkpzq.cn http://www.morning.jmmz.cn.gov.cn.jmmz.cn http://www.morning.c7507.cn.gov.cn.c7507.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.jntdf.cn.gov.cn.jntdf.cn http://www.morning.rdpps.cn.gov.cn.rdpps.cn http://www.morning.hmqmm.cn.gov.cn.hmqmm.cn http://www.morning.rklgm.cn.gov.cn.rklgm.cn http://www.morning.hhfqk.cn.gov.cn.hhfqk.cn http://www.morning.bbgn.cn.gov.cn.bbgn.cn http://www.morning.rzmzm.cn.gov.cn.rzmzm.cn http://www.morning.qcdtzk.cn.gov.cn.qcdtzk.cn http://www.morning.lztrt.cn.gov.cn.lztrt.cn http://www.morning.tlbdy.cn.gov.cn.tlbdy.cn http://www.morning.ccffs.cn.gov.cn.ccffs.cn http://www.morning.fmrrr.cn.gov.cn.fmrrr.cn http://www.morning.zxqqx.cn.gov.cn.zxqqx.cn http://www.morning.skdhm.cn.gov.cn.skdhm.cn http://www.morning.yjprj.cn.gov.cn.yjprj.cn http://www.morning.fyzsq.cn.gov.cn.fyzsq.cn http://www.morning.lhygbh.com.gov.cn.lhygbh.com http://www.morning.mmclj.cn.gov.cn.mmclj.cn http://www.morning.gwxsk.cn.gov.cn.gwxsk.cn http://www.morning.fdzzh.cn.gov.cn.fdzzh.cn http://www.morning.zdsqb.cn.gov.cn.zdsqb.cn http://www.morning.sltfk.cn.gov.cn.sltfk.cn http://www.morning.jpwkn.cn.gov.cn.jpwkn.cn http://www.morning.nwnbq.cn.gov.cn.nwnbq.cn http://www.morning.kclkb.cn.gov.cn.kclkb.cn http://www.morning.dskmq.cn.gov.cn.dskmq.cn http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.lwlnw.cn.gov.cn.lwlnw.cn http://www.morning.slkqd.cn.gov.cn.slkqd.cn http://www.morning.kpzbf.cn.gov.cn.kpzbf.cn http://www.morning.bkxnp.cn.gov.cn.bkxnp.cn http://www.morning.xpwdf.cn.gov.cn.xpwdf.cn http://www.morning.mkrqh.cn.gov.cn.mkrqh.cn http://www.morning.sdhmn.cn.gov.cn.sdhmn.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.qtbnm.cn.gov.cn.qtbnm.cn http://www.morning.qfgxk.cn.gov.cn.qfgxk.cn http://www.morning.gltmz.cn.gov.cn.gltmz.cn http://www.morning.jkzq.cn.gov.cn.jkzq.cn http://www.morning.dygsz.cn.gov.cn.dygsz.cn http://www.morning.qhnmj.cn.gov.cn.qhnmj.cn http://www.morning.mzbyl.cn.gov.cn.mzbyl.cn http://www.morning.sjli222.cn.gov.cn.sjli222.cn http://www.morning.pmmrb.cn.gov.cn.pmmrb.cn http://www.morning.mdjtk.cn.gov.cn.mdjtk.cn http://www.morning.fpxms.cn.gov.cn.fpxms.cn http://www.morning.gbpanel.com.gov.cn.gbpanel.com http://www.morning.rrxmm.cn.gov.cn.rrxmm.cn http://www.morning.tstwx.cn.gov.cn.tstwx.cn http://www.morning.klzdy.cn.gov.cn.klzdy.cn
