并查集路径压缩算法改进

并查集路径压缩算法改进

文章目录

​​优化find​​​​加权标记（改进merge）​​

大多数情况下，查询只关心根节点是谁，并不关心这棵树的形态，查询的时候，我们只要能判断两个节点的根节点是否相同即可

但是我们希望查询过程中，效率能稍微高一些。希望树能矮一点，这样我们从某个节点出发找根节点时，会更快速

假如当前的并查集如下，我们需要合并7和8所在树的根节点，我们从8出发找到根节点1，我们又从7出发经过相同的路径找到根节点1，然后我们发现根节点相同，不用合并，这样效率就很低了

优化find

我们进行如下优化：查询的时候将访问过的每个点的父节点修改成树根，这样的方法叫做路径压缩

由于无论是查询还是合并，我们都是操作根节点，修改后树变矮了，我们查找根节点更快，同时也不影响查询、合并的结果

查询的时候将访问过的每个点的父节点修改成树根，这样的方法叫做路径压缩

int find_root(int x) { if (x <= 0 || x >= SIZE) { return -1; } // 用于记录已经遍历过的节点 vector pos; while (x != parent[x]) { pos.push_back(x); x = parent[x]; } for (int p : pos) { parent[p] = x; } return x;}// 递归版本的查询int cur_find(int x) { if (x <= 0 || x >= SIZE) { return -1; } if (x == parent[x]) { return x; } else { // 查询的时候将访问过的每个点的父节点修改成树根 parent[x] = cur_find(parent[x]); return parent[x]; }}

find执行以后，后面的查询效率就很好，但美中不足的是，第一次执行find的效率不高，这需要使用加权标记方法优化

加权标记（改进merge）

为什么会产生上图那么高的树呢？因为我们merge的时候，父子关系一直都是一个方向

void merge(int x, int y) { x = cur_find(x); y = cur_find(y); if (x != y) { parent[y] = x; // x永远是y的父亲 // parent[x] = y; }}

对于以上的merge代码，我们如果按照如下的方式输入，并执行merge，就会产生图中的树

7 86 74 62 41 21 31 5

我们希望在构建并查集的过程中，进行集合合并的时候，能够使树能矮一点。我们使用加权标记的方式实现，使用一个height数组，记录每个节点的层高，下标则表示节点的编号

merge的时候，谁的height大，谁就作为父节点，由于我们只更新根节点的高度，在矮树挂在高树的情况下，根节点的高度不用更新

如果两棵树一样高，根节点合并以后，需要更新作为父亲的那棵树的根节点的height

再像上面一样输入，我们merge的时候，就能得到如下结构的并查集

// 合并x和y所在的集合void merge(int x, int y) { x = cur_find(x); y = cur_find(y); if (x != y) { // 这里x和y都是根节点，谁矮谁作为孩子节点 if (height[x] > height[y]) { parent[y] = x; } else { if (height[x] == height[y]) { // y作为合并以后树的根，根节点高度要+1 height[y]++; } parent[x] = y; } }}

用谁高谁当父亲的方式merge的时候，我们一直用单个节点往树中加入，这棵树一定只有两层

从单个节点开始构造并查集，使用谁高谁当父亲的方式merge，会得到两层的树。我们使用两个两层的树结合，两个根节点一样高，我们随便选取一个节点当父亲，更新该父节点的height即可（并不是更新所有节点的height），因为我们合并的时候只看根节点的高度。所以不是什么时候节点对应的height都是准的，可以保证的是，当前根节点的height是准的

比如我们按照如下的方式构造并查集，就会出现有的节点的height不准确

1 51 62 32 41 2

一般来说，在优化的merge中使用优化的find，在find的时候会改变树的结构，但find没有修改height，可能会导致当前根节点的height不准确，使用起来可能会不符合预期。所以我们不把merge加权优化和find优化放在一起使用

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。