数据结构之并查集

作者 : 开心源码 本文共6219个字,预计阅读时间需要16分钟 发布时间: 2022-05-13 共178人阅读

定义

并查集是计算机科学中为理解决集合之间的合并和查询操作而存在的一种树型数据结构。并查集是由若干个大小不同的子树来存储表示的,也可以把整个并查集的存储结构叫做森林,每颗子树表示一个集合。集合的数量又叫做连通分量

基本操作

  • find(查询):确定元素属于哪一个子集。它可以被用来确定两个元素能否属于同一子集。
  • union(合并):将两个子集合并成同一个集合。
  • isConnected(两个元素能否相连):确定两个元素能否属于同一子集或者者确定两个元素能否相连。

名词解释

  • 森林:由若干个大小不同的子树所表示的数据结构。
  • 连通分量:在这里简单的可以了解为并查集中集合的数量。
  • 树的大小:树的节点数量。
  • 树中某个节点的深度:该节点到树的根节点的路径上的链接数。
  • 树的高度:树中所有节点中的最大深度。

处理的问题

  • 在社交网络中判断两个人能否属于同一个交际圈。
  • 查询网络中的两个网络节点能否相连。
  • 数学中判断两个元素能否属于同一个集合。
  • 数学中把两个不相交的子集合并成一个集合。

并查集的实现

quick find

为每一个集合都选取一个元素做为该集合的唯一编号,假如有两个元素它们的编号相同,那么就说明它们属于同一个集合。

初始化

初始情况下假如有N个元素,我们认为这个N个元素之间都是相互独立的,也就是一共有N个集合,每个集合只有一个元素。定义一个叫做ids的数组用来存储每个集合的编号。每个集合的编号只要要保证不重复就可。可以循环N次为每个集合从0到N-1编号。

如图所示:

image

代码实现:

class UnionFind {private:    // 并查集中的元素个数    unsigned int elementNum = 0;   // 联通分量,也是集合的数量    unsigned int connectedComponent = 0;    // 存储每个集合的编号    int *ids;public:    UnionFind(unsigned int elementNum) {        this->elementNum = elementNum;        // 初始情况下联通分量为元素个数        this->connectedComponent = elementNum;        this->ids = new int[elementNum];        // 初始化每个集合的编号为0至size-1        for (int i = 0; i < elementNum; i++) {            this->ids[i] = i;        }    }};
查询

查询一个元素属于哪个集合,只要要查看这个元素的id。这也是为什么叫quick find,由于查询操作只要要O(1)的时间复杂度。

下图中0,1,2这三个元素的id都是0,元素3和元素4id分别是3和4。

image

代码实现:

int find(element) {    return this->ids[element];}
两个元素能否相连

判断两个元素能否属于同一个集合时,只要要比照两个元素的id能否相等就可。

下图中0,1,2这三个元素的id都是0,所以它们是相连的。节点3和元素0,1,2都不相连,由于它们id不同。

image

代码实现:

bool isConnected(int p ,int q) {    return this->find( p) == this->find(q); }
合并

合并两个集合时,只要要把任意其中一个集合中的所有元素的id修改成另外一个集合的id就可,这样一来原价的两个集合都指向了同一个id,就完成了合并操作。

image

假如我们需要把上图中元素3和元素2合并,就有两个办法分别是:

  • 把元素2所在的集合的所有元素的id修改成元素3所在集合的id

    image

  • 把元素3所在的集合的所有元素修改成元素2所在集合的id

image

不论选择哪一种方法最终所表示的集合都是等价的,所以两种方法都可以。

代码实现:

void unionElement(int p, int q) {    int pId = this->find(p);    int qId = this->find(q);    // 假如p和q原本就相连就不需要合并    if (pId == qId) {        return;    }    for (int i = 0; i < this->size; i ++) {        // 把其中一个集合中的所有元素的id修改成另外一个集合的id        if  (this->id[i] == pId) {            this->ids[i] = qId;        }    }    // 合并之后少了一个集合,connectedComponent就应该-1    this->connectedComponent --;}

quick find这种实现方式,它的优点在于可以快速的查询元素属于哪一个集合。缺点是在每次做合并的时候都需要遍历整个ids数组而后去修改其中一个集合的所有元素的id,这样就会导致合并操作在数据量大的时候时间复杂度很高。

quick union

把每个元素看成一个节点,每个节点指向该节点的父节点。这一点跟传统的树行结构不太一样,传统的树行结构是节点指向该节点的孩子节点。并查集中的每棵树都表示一个集合,整个并查集所表示的就是一个森林。每棵树会选取一个节点作为代表,用来代表这棵树所表示的集合,这个代表节点也是树的根节点。假如两个元素的根节点相同则它们属于同一棵树也就是属于同一个集合。

初始化

初始情况下,我们还是认为每个元素(节点)之间相互独立,每棵树只有一个根节点就是其本身,这个根节点用来代表这棵树所表示的集合。定义一个叫做parents的数组用来存储每个节点的父节点。

如图所示:

image

代码实现:

class UnionFind {private:    // 并查集中的元素个数    unsigned int elementNum = 0;    // 联通分量,也是集合的数量    unsigned int connectedComponent = 0;    // 存储每个节点的父节点    int *parents;public:    UnionFind(unsigned int elementNum) {        this->elementNum = elementNum;        // 初始情况下联通分量为元素个数        this->connectedComponent = elementNum;        this->parents = new int[elementNum];        // 初始化每个节点的父节点是其本身        for (int i = 0; i < elementNum; i++) {            this->parents[i] = i;        }    }};
查询

查询一个元素属于哪个集合,只要要查看该元素所在树的根节点的那个元素是谁,就属于哪个集合。

下图中0,1,2,3这四个元素的根节点都是0,元素3根节点是3。整个并查集是由两棵树组成的一个森林。

image

假如要查询节点3属于哪一个集合就需要在parents数组中递归去寻觅树的根节点,直到找到某个节点的父节点是其本身的一个节点,这个节点就是树的根节点。

递归实现:

int find(element) {    int parent = parents[element];    // 假如某个节点的父节点是其本身的一个节点,那么就是一个根节点    if (parent == element) {        return parent;    }    // 继续递归查询    return this->find(parent);}

循环实现:

int find(element) {    while (parents[element]  != element) {       element =  parents[element];    }    return element;}
两个元素能否相连

判断两个元素能否属于同一个集合时,只要要比照两个元素所在树的根节点能否能否是同一个节点就可。

下图中0,1,2,3这四个元素的根节点都是0,证实它们属于同一棵树且相连。元素3根节点是3。所以节点3和元素0,1,2,3都不相连,由于它们的根节点不同。

image

代码实现:

bool isConnected(int p ,int q) {    return this->find( p) == this->find(q); }
合并

合并两个集合时,只要要把其中任意一颗树的根节点的父节点修改成另一个颗树的根节点,这样一来原价两颗树的根节点都是同一个节点,就完成了合并操作。

下图中有两个集合,包含的元素分别是0,1,2,34,5,6。对应的两棵树的根节点分别是04。当合并这两个集合时,我们可以把这两棵树中的任意一棵树的根节点的父节点修改成另一棵树的根节点即可以完成合并操作。

image

我们把根节点为4的这棵树的根节点的父节点修改成0,就合并成了一个集合。树的形状也就变成了下面这个样子:

image

代码实现:

    void unionElement(int p, int q)  {        int pRoot = this->find(p);        int qRoot = this->find(q);                // 假如两个元素的根节点相同,则代表它们属于同一个集合,就不再需要合并        if ( pRoot == qRoot )  {            return;        }        // 修改其中一棵树根节点的父节点        this->parents[qRoot] = pRoot;       // 合并之后少了一个集合,connectedComponent就应该-1        this->connectedComponent --;    }    

加权quick union

quick union合并时存在的问题

下图中两棵树所表示的集合相同,都分别表示的是拥有0,1,2,3,4这5个元素的一个集合。

image

左边树中节点4的深度为3,而右边树中节点4的深度则为1。通过quick unionfind的实现可以知道,当在左边树中执行find(4)时需要的时间复杂度是要高于右边树中执行find(4)的,由于。所以得出一个结论就是:quick union中的find操作的时间复杂度是跟要查找节点在树中的深度相关的。find操作需要一直向上寻觅根节点,假如要查找的节点在树中深度很深,那么需要寻觅根节点的次数也就会越多。

优化思路

因为在quick union中对两个集合进行union操作时,不论是哪棵树的根节点的父节点修改成另外一棵树的根节点最终所得到的新树所表示的集合都是等价的。

所以我们可以在union操作时把树的高度较小的那棵树的根节点的父节点修改成树的高度较大的那颗树的根节点,在两棵树的高度相等时,就跟先前一样不论是哪棵树的根节点的父节点修改成另外一棵树的根节点最终所得到的新树所表示的集合和新树的高度都是一样的。

优化思路证实

存在两颗树分别是AB,它们树的高度分别是AhBhAh <Bh。我们有两种办法可以来完成union操作,分别是:

  • A的根节点的父节点修改成树B的根节点(优化思路)

    修改之后因为在原来树A的根节点新添加了一个节点,所以在新的树中原来树A的高度为Ah+1。因为Ah <Bh,所以Ah+1<=Bh。得到新树的最大深度为Bh

  • B的根节点的父节点修改成树A的根节点

    修改之后因为在原来树B的根节点新添加了一个节点,所以在新的树中原来树B的高度为Bh+1。因为Ah <Bh,所以Ah<Bh+1。得到新树的最大深度为Bh+1

得到结果Bh<Bh+1即可以证实我们的优化思路是可以降低节点在树中的深度的。

具体实现

初始化的时候跟quick union一样,只是多了数组用来存放每个节点的深度,我们定义这个数组叫ranks。初始化情况下我们让每个节点在树中的深度为1findisConnected的实现跟之前的quick union一样。

代码实现:

class UnionFind {private:    // 并查集中的元素个数    unsigned int elementNum = 0;    // 联通分量,也是集合的数量    unsigned int connectedComponent = 0;    // 存储每个节点的父节点    int *parents;    // 记录每个根节点所在树的深度    int *ranks;public:    UnionFind(unsigned int elementNum) {        this->elementNum = elementNum;        // 初始情况下联通分量为元素个数        this->connectedComponent = elementNum;        this->parents = new int[elementNum];        this->ranks = new int[elementNum];        for (int i = 0; i < elementNum; i++) {            // 初始化每个节点的父节点是其本身            this->parents[i] = i;            this->ranks[i] = 1;        }    }    // 合并元素    void unionElement(int p, int q) {        int pRoot = this->find(p);        int qRoot = this->find(q);        // 假如两个元素的根节点相同,则代表它们属于同一个集合,就不再需要合并        if (pRoot == qRoot) {            return;        }        int pRank = this->ranks[pRoot];        int qRank = this->ranks[qRoot];        // 把深度低的树的根节点指向深度高的树的根节点。        if (pRank > qRank) {            this->parents[qRoot] = pRoot;        } else if (pRank < qRank) {            this->parents[pRoot] = qRoot;        } else {            this->parents[pRoot] = qRoot;            this->ranks[qRoot]++;        }        // 合并之后少了一个集合,connectedComponent就应该-1        this->connectedComponent --;    }};

路径压缩

最优树结构

通过我们优化之后的加权quick union还是没有达到我们最优树结构。下图的两棵树都表示的是两个相同的集合。左边树中的每个节点与根节点的距离大于等于1。右边树中的每个节点与根节点的距离等于1,也就是我们想要的最优树结构。

image

我们需要一个算法要压缩路径使得树中的每个节点与根节点的距离为1

路径压缩思路

把某个节点的父节点修改成该节点父节点的父节点,一直向上对这条链接上的每个节点做相同的操作直到遇到根节点终止,即可以压缩每个节点到根节点的距离。

路径压缩过程演示

左边树中节点4的父节点的父节点是2,所以把左边树中节点4的父节点修改成2,得到右边的树:

image

左边树中节点4的父节点的父节点是0,所以把左边树中节点4的父节点修改成0,得到右边的树:

image

左边树中节点3的父节点的父节点是0,所以最后把左边树中节点3的父节点修改成0,就得到右边的树:

image

这样一番操作之后最终得到结果就是我们想要的树结构。

具体实现

因为路径压缩的过程跟find操作有些相似,都是向上寻觅节点,且都是遇到根节点终止,所以把路径压缩的过程就直接放在了find操作中。union操作不需要做任何改动。

find代码实现:

    int find(int element) {        int parent = parents[element];        if (parent == element) {            return parent;        }        // 路径压缩,parents[parent]得到的就是当前节点父节点的父节点        parents[element] = parents[parent];        return this->find(parents[element]);    }

完整源代码

源代码: acodercat/cpp-algorithms/blob/master/include/union_find.h

使用示例: acodercat/cpp-algorithms/blob/master/src/demo/union_find.cpp

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 数据结构之并查集

发表回复