并查集详解：合并、查找与Kruskal算法应用
并查集详解：合并、查找与Kruskal算法应用
并查集（Disjoint Set）是一种用于处理不相交集合的数据结构，广泛应用于图论、网络分析等领域。本文将详细介绍并查集的定义、基本操作、优化方法以及实际应用，帮助读者全面理解这一重要数据结构。
并查集的定义
英文：Disjoint Set，即不相交集合；将编号为1到N的N个元素划分为若干个不相交集合，在每个集合中，选择集合中的某个元素代表其所在集合。
之所以称为并查集是因为其常见的两种操作：
- 合并两个集合
- 查找某元素属于哪个集合
并查集基本操作
实现方法
例如，用编号最小的元素标记其所在集合。定义一个数组Set[1…n]，其中Set[i]表示元素i所在集合。
Set(i) = {1，2，1，4，2，6，1，6，2，2}
不相交集合：{1，3，7}，{4}，{2，5，9，10}，{6，8}
基本操作
1.查找
find(x)
{
return Set[x];//元素自己就代表所在集合
}
时间复杂度为O(1)
2.合并
merge(a,b)
{
i = min(a,b);
j = max(a,b);
for(int k = 1; k <= N; k++)//遍历所有元素
{
if(Set[k] == j)
Set[k] = i;//将所有“老大”为j的元素改为i，即i为合并后的新集合的代表元素
}
}
时间复杂度为O(N)
优化
实现方法
每个集合用一颗“有根树”表示。定义数组Set[1…n]，其中Set[i]表示元素i的父节点。
Set = {1,2,3,2,1,3,4,3,3,4}
基本操作
1.查找
代码不变，由于并查集的实现方式改变，效率有所提升
find(x)
{
r = x;
while(Set[r] != r)//不是根节点
r = Set[r];//变为其父节点
return r;;
}
时间复杂度的最坏情况为O（N）
2.合并
merge(a,b)
{
Set[a] = b;//将b变为a的父节点即可
}
时间复杂度为O（1）
运行效率较原先有所提升，但我们需要避免查找算法出现最坏情况。方法：将深度小的树合并到深度大的树（这样查找的树的最大深度不会增加）
3.查找
find(x)
{
r = x;
while(Set[r] != r)
r = Set[r];
return r;
}
最坏情况为O（logN）
4.合并（优化）
merge(a,b)
{
if(height(a) == height(b))
{
height(a) = height(a) + 1;//当两树层数相同时，任一树层数+1，并成为另一节点的父节点
Set[b] = a;
}
else if(height(a) < height(b))//a树层数小于b
Set[a] = b;
else
Set[b] = a;
}
O(1)
进一步优化查找方法（路径压缩）
思想：每次查找将路径缩短，以便下次查找速度更快
方案：
- 找到根节点
- 修改路径上所有节点，将他们都指向跟节点
在不断查找的过程中不断缩短路径，整棵树将趋于扁平（层数减少）
代码实现
find(x)
{
if(Set[x] != x)
Set[x] = find(Set[x]);//递归将路过的所有节点直接指向跟节点
return Set[x];
}
例题
题目描述：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
经过思考不难得知答案为 集合数 - 1
#include <stdio.h>
int bin[1002];
int find(int x)
{
int r=x;
while(bin[r]!=r)
r=bin[r];
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx = findx(x);
fy = findx(y);
if(fx != fy)
bin[fx] = fy;
}
int main()
{
int n,m,i,x,y,count;
while(scanf("%d", &n),n)
{
for(i=1;i<=n;i++)//并查集初始化，所有元素最开始都指向自己，所有元素的老大都是自己
bin[i] = i;
for(scanf("%d", &m);m > 0;m--)
{
scanf("%d%d", &x, &y);
merge(x,y);
}
for(count=-1, i=1;i<=n;i++)//count初始化为-1，输出时不需要再-1
if(bin[i] == i)//根节点指向自己
count ++;//集合数量+1
printf("%d\n", count);
}
return 0;
}
经典应用：最小生成树（Kruskal算法）
算法过程为贪心思想，每次找到权值最小的边，如果该边连接的两个顶点不都在集合内（不会形成环），则将该边加入集合，否则，找下一条权值最小的边。