理解Kruskal算法的前提----深入理解并查集【超简单~】

并查集的实现思路

并查集主要分为两个部分：第一部分就是需要找到点对应的祖宗节点，第二部分，是要将属于同一个集合节点的祖宗节点进行统一，也就是结合操作。

Find函数实现

// parent数组用来存储下标值所对应的父节点值
// 比如：parent[i]=k,表示编号为i节点的父节点是编号为k的节点
int find(vector<int> &parent, int i){
	if(parent[i]==-1){ //如果i节点没有父节点，那么它自己就是它的祖宗节点（换句话说，也就是找到了最终的祖宗节点）
		return i;
	}
	return find(parent,parent[i]); // 如果i节点有上一级节点，就按照该线索（它的父亲）继续向上寻找，直到找到祖宗节点为止。
}
1
2
3
4
5
6
7
8

Union函数实现

void Union(vector<int> &parent, int i, int j){
	int p_i = find(parent,i); // 找到i的祖宗节点
	int p_j = find(parent,j); // 找到j的祖宗节点
	parent[p_i] = p_j; // 这里可以随便写，谁想当祖宗都可以（合并i,j的祖宗节点）
	return ;
}
1
2
3
4
5
6