【数据结构】图论与并查集

一、并查集

1.原理

1. 简单的讲并查集，就是查询两个个元素，是否在一个集合当中，这里的集合用树的形式进行表示。
2. 并查集的本质就是森林, 即多棵树。

 ���们再来简单的举个例子:

• 假设此时的你是大一新生，刚进入大学，肯定是先找到宿舍在哪里，然后跟寝室里面的舍友互相认识一下，先形成一个小团体。
• 假设，宿舍总共6个人，也就是6个人的集合。几乎所有的大学生都是这样先跟周围的人进行联系起来的。
• 然后辅导员召集班会，这时的你欣然前往，并在讲台上自信的介绍自己，然后吸引或者主动又认识了一群人。这时你或许又跟其它的人进行了关联，或成为了好友，或成为了恋人……

  下面我们用如上例子进行展开讨论：

  • 宿舍六人，即六个人，如何判断两个人在同一个集合？ 如何进行实现？
    1. 先来解决第一个问题，六个人，选出一个宿舍长，只要两个人的宿舍长是一样的，即可判断两个人在一个集合。
    2. 再来解决第二个问题，既然宿舍长有了，我们都与这个宿舍长产生关联即可，即用树的形式进行表示，至于如何表示，我们可以用双亲表示法进行表示，即每个人记住其宿舍长的名字即可。更为形象的我们可以用下图进行表示：
    3. 更进一步，如何用计算机存储这种结构呢？我们只需对每个人名生成一个下标连续，用计算机进行存储即可。用下图进行直观的理解：
    4. 对这张图我们再说明一点，除0下标以外的其他位置存放的是指向代表孙八的下标，这个0处下标存的是集合的所有元素的个数，且存放的是负数形式，这样存有一个好处，我们可以由这个并查集中有多少负数，从而判断这个并查集中有多少个集合。
    • 两个人产生关联，本质上是两个宿舍(集合)之间产生了关联，那两个宿舍如何进行关联起来呢？
      • 下面我们以图的形式更为清晰的进行表述：
      • 也就是说因为宿舍的成员是以宿舍长联系起来的，那宿舍与宿舍之间，产生关联(合并)，就宿舍长之间认识一下，两个集合就间接的关联起来了。
      • 下图是具体的存储方式：

        2.基本实现

         根据上面的描述，我们可以作出大致总结：

        1. 数组进行存储表示树形结构。
        2. 数组的下标对应着具体的信息(人名，编号等)。
        3. 我们可以通过一个元素的下标的值不断往上查找，直到找到找到小于0的，即为根节点所在的位置。
        4. 数组中负数的个数代表着集合的个数。
        5. 判断两个元素是否在同一个集合，只需找到根的下标判断是否相等即可。
        6. 将两个不同集合进行合并，其实就是找到根，然后进行更改一个根的指向与改变另一个根的元素个数即可。

        由以上信息我们先可以搭建出实现并查集的大致框架：

        2.1.基本框架

        #include#include#includeusing namespace std;templateclass UnionFindSet{public:UnionFindSet(const T* arr, size_t size);//构造函数int GetValueIndex(const T& val);//获取val所代表的下标。void GetRoot(const T& val);//获取根节点的下标void Union(const T& x1, const T& x2);//将两个元素的集合进行合并。bool IsSameSet(const T& x1, const T& x2);//判断两个元素是否在同一个集合中int GetSetSize(); //获取集合的元素private:map _indexHash;//map或者unordered_map都可以。用于快速将T转换为对应的下标。vector _createIndex;//用此数组对T类型元素生成下标。vetor _aggregate; //用于存放集合元素，即森林。};

        2.2.构造函数

        UnionFindSet(const T* arr, size_t size){_aggreagte.resize(size, -1);//对存放集合的元素初始化，表示每个元素存放一个元素(负数表示)。_createIndex.resize(size);for (size_t i = 0; i  
        2.3.转换元素为下标
         
        int GetValueIndex(const T& val){auto it = _indexHash.find(val);//最好判断一下val是否存在对应的下标。if (it == _indexHash.end()){throw invalid_argument("不存在所对应的下标");return -1;}return it->second;}
         
        2.4.获取元素根节点下标
         
        int GetRoot(const T& val){int index = GetValueIndex(val);//找不到小于0的下标指向的位置就一直向上进行找。while (_aggregate[index] >= 0){index = _aggregate[index];}return index;}
         
        2.5.判断元素集合是否相同
         
        bool IsSameSet(const T& x1, const T& x2)/{int index1 = GetRoot(x1);int index2 = GetRoot(x2);return index1 == index2;}
         
        2.6.合并元素集合
         
        void Union(const T& x1, const T& x2)//将两个元素的集合进行合并。{if (!IsSameSet(x1, x2)){//不在同一个集合再进行合并。int index1 = GetRoot(x1);int index2 = GetRoot(x2);//进行一步优化，即元素少的合并到元素多的集合当中//此处我们假设index1为元素多的集合，index2为元素少的集合。if (abs(index1)  
        2.7.获取集合个数
         
        int GetSetSize()//获取并查集的集合个数{int sum = 0;for (auto e : _aggregate){//计算小于0的元素个数即可。if (e  
        3.路径压缩
         
         所谓路径压缩，其实解决存在这样的集合：
        所引发的问题：如果数据足够的多，我们之前写的GetRoot函数的效率会急剧的降低，因此才需要路径压缩帮助我们进行优化。
         
        实现方式也很简单：
         

        • 我们只需要找到根节点之后，再找一遍，此时将cur路径上的结点链接到root即可，这样方便了后续的查找。

        • 优化之后的GetRoot

          int GetRoot(const T& val)//获取根节点的下标{int index = GetValueIndex(val);int root = index;//找不到小于0的下标指向的位置就一直向上进行找。while (_aggregate[root] >= 0){root = _aggregate[root];}//路径压缩进行优化。while (index != root){//先保存之前父路径的下标int parent = _aggregate[index];//再将当前结点的父路径改为root_aggregate[index] = root;//继续往上迭代index = parent;}return root;}

          4.源码与测试

          • UnionFindSet.hpp

            #include#include#includeusing namespace std;templateclass UnionFindSet{public:UnionFindSet(const T* arr, size_t size){_aggregate.resize(size, -1);//对存放集合的元素初始化，表示每个元素存放一个元素(负数表示)。_createIndex.resize(size);for (size_t i = 0; i second;}int GetRoot(const T& val)//获取根节点的下标{int index = GetValueIndex(val);int root = index;//找不到小于0的下标指向的位置就一直向上进行找。while (_aggregate[root] >= 0){root = _aggregate[root];}//路径压缩进行优化。while (index != root){//先保存之前父路径的下标int parent = _aggregate[index];//再将当前结点的父路径改为root_aggregate[index] = root;//继续往上迭代index = parent;}return root;}void Union(const T& x1, const T& x2)//将两个元素的集合进行合并。{if (!IsSameSet(x1, x2)){//不在同一个集合再进行合并。int index1 = GetRoot(x1);int index2 = GetRoot(x2);//进行一步优化，即元素少的合并到元素多的集合当中//此处我们假设index1为元素多的集合，index2为元素少的集合。if (abs(index1)  

            • Test.cpp

              #include"UnionFindSet.hpp"int main(){string str[] = { "张三","李四","王五","赵六","周七" };UnionFindSet ufs(str, sizeof(str) / sizeof(str[0]));ufs.Union("张三", "李四");ufs.Union("王五", "赵六");cout public:/*构造函数，传入的参数为V类型的指针指向的是V类型数组，以及数组的元素个数。*/Graph(const V* a, size_t n)//有多少个顶点{//初始化边，以及生成边的下标_vertexs.resize(n);for (size_t i = 0; i