| 并查集C++实现及优化（以朋友圈子为例） | 您所在的位置：网站首页 › 数据结构与算法的基本思路 › 并查集C++实现及优化（以朋友圈子为例） |
并查集C++实现及优化（以朋友圈子为例）
|
“并查集"去年加入了考纲，正好之前在准备比赛时也看了一下这个算法，然后也学习王道的数据结构，所以总结一下。 文章目录 并查集基本概念（Union-Find-Disjoint）存储结构雏形Union优化思路和疑惑Union优化后代码 Find优化Find优化后代码（递归与非递归实现） 完整代码一个小demo——朋友圈归类一些应用展望总结在接触这个算法之前，怎么根据关系划分圈子一直困扰着我，之前想实现一下QQ空间的效果，而这个算法提供拓宽了我的思路（希望各位大佬更大地帮我拓宽思路）。 OK，先从概念开始。 并查集基本概念（Union-Find-Disjoint）并查集，旨在将集合中有关联的元素，连接到一块形成一棵树，当然，由于联系有很多很多可能，所以最终可能存在着多棵互不交集的树。 “查”：指的是查找某个结点的根节点。 “并”：指的是合并两个不一样的根节点。 “集”：指的是集合。 举个不是很恰当的小例子：朋友关联圈子 有一个人与我加好友，这就与我构成一个联系， 而另外一个人与我加好友，也与我构成了一个联系， 与我有联系的朋友与我相联，这样我就有了一个朋友关联圈子。 当然，我的朋友可能与别人也有联系（或是有一些跟我和我的朋友们毫无关系的人。） 而并查集能实现的是将它们归类，如下图，归成了两部分， 上图是Find没经过优化的。 下图是上图左边那颗树优化后的结果（一步到位找到我）。 那么应该怎么存储合适？双亲表示法真是个很棒的思路。 存储结构使用双亲表示法来存储，也就是节点内存双亲。 需要两个结构体实现，一个是定义类似数组的结构，用于存储节点, 一个是定义每个节点的结构。 //节点结构 typedef struct PTNode{int data;int parent; }PTNode; //顺序表 typedef struct PTree{struct PTNode notes[MAXSIZE];int n; }PTree;简单模拟操作，我们可以直接用数组代替就行，因为数组本质上就是这样一种结构（顺序表+存数据的节点） int UFset[MAXSIZE]; // 如果存储的值为 -1表示该节点为根节点。（有些人是初始化为下标，都行） // 如果存储的值为其他正数，表示该节点的父亲节点的下标为该数字 雏形 //初始化 bool Init(int s[]){for(int i=0;i//根节点的parent被初始化为-1,所以可以以此为依据查找根节点while(s[i]>0){i = s[i]; }return i; } //并，合并不同根节点 bool Union(int s[],int root1,int root2){//这里显然不能用s[root1] == s[root2]，因为初始时都是-1，除非按照下标初始化 if(root1==root2) return false;else s[root1] = root2; return true; }简单测试 //两个根节点合并 int main(){Init(UFset); int root1 = find(UFset,1); int root2 = find(UFset,2);printf("%d,%d\n",root1,root2);Union(UFset,root1,root2);//root1并到root2printf("%d,%d\n",UFset[1],UFset[2]);return 0; }
原Union出现的问题：我们在对于两个根节点并合的时候，可能会导致一棵树的高度不断增高，树高度增高会导致Find查找速度变慢（因为Find会从该节点一直往上找，直到找到根节点）,最坏时间复杂度达O(n^2) 优化方式 将小树主动连到大树上。 怎么判断谁是小树，谁是大树？ 利用好根节点（原本存的是-1），负数的绝对值可以表示该树有多少个节点。 优化后的Union：高度不会增长的如同原Union那么快, 树的高度不会超过⌊logn⌋+1,Find最坏时间复杂度O(logn)
自然想到，一个很肥，但节点数多，一个很高，但节点数少，二者合并，如下图，看起来好像应该并到小树？ 优化前寻找根节点需要从当前节点不断找向上找双亲节点，将寻找根节点时,路过的节点的双亲节点都设置成根节点（即直连根节点），以后，寻找某个结点的根节点时仅需一步，如下图。 （完成后，寻找3、2节点的根节点，可以一步就找到是1） 非递归实现 int find(int s[],int i){int root = i; //找到根节点（代表节点） while(s[i]>0) root = s[i];//将沿途节点的父节点都设置为父节点 (路径压缩)while(i!=root){int t = s[i]; //将该节点父节点暂存 s[i] = root; //将该节点父节点设为root （即直连根节点）i = t; //指向下一个节点（该节点原父节点） } return root; //返回根节点编号 }递归实现 int find(int s[],int i){if(s[i] //此操作称为路径压缩，目的是将路径的父节点都赋值为根节点s[i] = find(s,s[i]);return s[i];} } 完整代码（非递归实现） include #define MAXSIZE 100 using namespace std; int UFset[MAXSIZE]; /* typedef struct PTNode{int data;int parent; }PTNode; typedef struct PTree{struct PTNode notes[MAXSIZE];int n; }PTree; */ //初始化操作 bool Init(int s[]){for(int i=0;iint root = i; //找到根节点（代表节点） while(s[i]>0) root = s[i]; //将沿途节点的父节点都设置为父节点 (路径压缩)while(i!=root){int t = s[i]; //将该节点父节点暂存 s[i] = root; //将该节点父节点设为root i = t; //指向下一个节点（原父节点） } return root; //返回根节点编号 }//"并"操作 bool Union(int s[],int root1,int root2){//这里显然不能用s[root1] == s[root2]，因为初始时都是-1，除非按照下标初始化 if(root1==root2){return false; }else{//代表点（顶点）为负数值，所以要反着比 if(s[root1]>s[root2]){s[root2] += s[root1];s[root1] = root2; }else{//1.初始化时 2.以及子节点数更多的在root1时（绝对值） s[root1] += s[root2];s[root2] = root1; }}return true; }int main(){Init(UFset); int root1 = find(UFset,1);int root2 = find(UFset,2);printf("%d,%d\n",root1,root2);Union(UFset,root1,root2);printf("%d,%d\n",UFset[1],UFset[2]);return 0; } 一个小demo——朋友圈归类实现的效果只是将关系分类。 #include using namespace std; #define MAXSIZE 100 //人 class Person{public:Person(string name);string getName();int getAge();void setName(string name);void setAge(int age);private:string name;int age; }; Person::Person(string name){this->name = name; } int Person::getAge(){return this->age; } string Person::getName(){return this->name; } //节点结构（每个人的信息） typedef struct PTNode{Person* someone;int index;int parent; }PTNode; //顺序表(朋友关系链) typedef struct PTree{struct PTNode *notes;int n; }PTree; //初始化 bool Init(PTree &T,string names[],int num){for(int i=0;iif(T.notes[i].parent //此操作称为路径压缩，目的是将路径节点的父节点都赋值为祖先节点T.notes[i].parent = find(T,T.notes[i].parent);return T.notes[i].parent;} } //"并"操作 bool Union(PTree &T,int root1,int root2){//判断是否是同个根节点 if(root1==root2){return false; }else{//代表点（顶点）为负数值，所以要反着比 if(T.notes[root1].parent> T.notes[root2].parent){T.notes[root2].parent += T.notes[root1].parent;T.notes[root1].parent = root2; }else{T.notes[root1].parent += T.notes[root2].parent;T.notes[root2].parent = root1; }}return true; }int main(){int r_n,num;string p1,p2;map namemap;PTree T;coutcin>>p1>>p2;int root1 = find(T,namemap[p1]);int root2 = find(T,namemap[p2]);Union(T,root1,root2);}//打印for(int i=0;icout |
优化角度更多了从并操作和查操作角度进行，下面进行Union优化，这个过程也有些小疑惑。
那我一定要大树并小树呢？
可能会想到，究竟何为大树，何为小树？可以认为是结点数量吗？不用考虑高度？
事实上，上图右边那种树如果按照这个规律构建，即小树根节点都接到了大树根节点上，并不会生成右边这种直挺挺的树，而是左边那种胖胖的树 因此，可以归结成节点数量多为大树，小树根节点该并入大树根节点。
【本文地址】