并查集C++实现及优化（以朋友圈子为例）

目前在准备考研，“并查集"去年加入了考纲，正好之前在准备比赛时也看了一下这个算法，然后也学习王道的数据结构，正好总结一下，当做我的第一篇博客吧。

• • 并查集基本概念（Union-Find-Disjoint）
  • 存储结构
  • 雏形
  • Union优化
  • • 思路和疑惑
    • Union优化后代码
  • Find优化
  • • Find优化后代码（递归与非递归实现）
  • 完整代码
  • 一个小demo——朋友圈归类
  • 一些应用展望
  • 总结

在接触这个算法之前，怎么根据关系划分圈子一直困扰着我，之前想实现一下QQ空间的效果，而这个算法提供拓宽了我的思路（希望各位大佬更大地帮我拓宽思路）。
OK，先从概念开始。

并查集，旨在将集合中有关联的元素，连接到一块形成一棵树，当然，由于联系有很多很多可能，所以最终可能存在着多棵互不交集的树。

“查”：指的是查找某个结点的根节点。

“并”：指的是合并两个不一样的根节点。

“集”：指的是集合。

举个不是很恰当的小例子：朋友关联圈子

有一个人与我加好友，这就与我构成一个联系，

而另外一个人与我加好友，也与我构成了一个联系，

与我有联系的朋友与我相联，这样我就有了一个朋友关联圈子。

当然，我的朋友可能与别人也有联系（或是有一些跟我和我的朋友们毫无关系的人。）

而并查集能实现的是将它们归类，如下图，归成了两部分，

上图是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
		s[i] = -1; //有些是初始化为下标，都行（即s[i] = i）
	}
	return true;
}
//查，查根节点
int find(int s[],int 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,%dn",root1,root2);
	Union(UFset,root1,root2);//root1并到root2
	printf("%d,%dn",UFset[1],UFset[2]);
	return 0;
}

优化角度更多了从并操作和查操作角度进行，下面进行Union优化，这个过程也有些小疑惑。

原Union出现的问题：我们在对于两个根节点并合的时候，可能会导致一棵树的高度不断增高，树高度增高会导致Find查找速度变慢（因为Find会从该节点一直往上找，直到找到根节点）,最坏时间复杂度达O(n^2)

优化方式

将小树主动连到大树上。

怎么判断谁是小树，谁是大树？

利用好根节点（原本存的是-1），负数的绝对值可以表示该树有多少个节点。

优化后的Union：高度不会增长的如同原Union那么快, 树的高度不会超过⌊logn⌋+1,Find最坏时间复杂度O(logn)

那我一定要大树并小树呢？

可能会想到，究竟何为大树，何为小树？可以认为是结点数量吗？不用考虑高度？

自然想到，一个很肥，但节点数多，一个很高，但节点数少，二者合并，如下图，看起来好像应该并到小树？

事实上，上图右边那种树如果按照这个规律构建，即小树根节点都接到了大树根节点上，并不会生成右边这种直挺挺的树，而是左边那种胖胖的树
因此，可以归结成节点数量多为大树，小树根节点该并入大树根节点。

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; //小树根root1并到大树根root2 
		}else{ 
			s[root1] += s[root2]; //节点数累加
			s[root2] = root1; //小树根root2并到大树根root1（或两棵同样大小的树）
		}
	}
	return true;
}

优化前寻找根节点需要从当前节点不断找向上找双亲节点，将寻找根节点时,路过的节点的双亲节点都设置成根节点（即直连根节点），以后，寻找某个结点的根节点时仅需一步，如下图。
（完成后，寻找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] < -1){
        	return i;
		}else{
    		//此操作称为路径压缩，目的是将路径的父节点都赋值为根节点
        	s[i] = find(s,s[i]);
        	return s[i];
		}
}

（非递归实现）

include
#define MAXSIZE 100
using namespace std;
int UFset[MAXSIZE];

//初始化操作
bool Init(int s[]){
	for(int i=0;i
		s[i] = -1;
	}
	return true;
}

//"查"操作
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; //返回根节点编号 
}

//"并"操作
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,%dn",root1,root2);
	Union(UFset,root1,root2);
	printf("%d,%dn",UFset[1],UFset[2]);
	return 0;
}

实现的效果只是将关系分类。

#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;i
		T.notes[i].someone = new Person(names[i]);
		T.notes[i].index = i;
		T.notes[i].parent = -1;
	}
	return true;
}
//"查"操作
int find(PTree &T,int i){
 	if(T.notes[i].parent <=-1){
    	return i;
	}else{
		 //此操作称为路径压缩，目的是将路径节点的父节点都赋值为祖先节点
    	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;
	cout<<"输入人数:"<>num; 
	string names[MAXSIZE];
	T.notes =(PTNode*) malloc(sizeof(PTNode)*num);
	cout<<"输入他们的名字"<
		cin>>names[i];
		namemap[names[i]] = i;
	}
	Init(T,names,num);
	cout<<"关系数量:"<>r_n;
    //对关系进行归类
	for(int i=0;i
		cin>>p1>>p2;
		int root1 = find(T,namemap[p1]);
		int root2 = find(T,namemap[p2]);
		Union(T,root1,root2);
	}
	//打印
	for(int i=0;i
		if(T.notes[i].parent<-1){
			cout<getName()<<"(其拥有朋友圈树有节点数="<
			cout<getName()<<",";
		}
	}
	return 0;
}

结果：

并查集完成后，可以给根节点设置一个编号（通过哈希值去算），
数据库根据编号创建一个表（异或是说设一个编号字段），
然后这棵树上的节点可以根据这个编号去，共享操作这个表（或者这个编号字段），
感觉像是个群聊记录存储（或者圈子消息）。
后面有空再尝试看看能不能实现。

1. 并查集能够实现快速将关联关系并入对应树中。
2. 每课树都有一个代表性的节点（即根节点）。
3. Union优化，是将节点数少的树并到节点大的树，这样可以保持树的高度不会太高。
4. Find优化后，整棵树的节点都会接到这个代表性节点。

不过就仔细想想，好像并查集Find优化后，只需要一步就到达根节点，但是这样也失去了每个节点找到其原父节点这个特性。

由于目前所学尚浅，有更好更简单实现方式，还请各位大佬指教。