06并查集(最小生成树).ppt

第七讲
并查集(Disjoint Set)
导引问题(1798)
在某个城市里住着n个人,现在给定关于 n个人的m条信息(即某2个人认识),

假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?
如何实现?
什么是并查集?
英文:Disjoint Set,即“不相交集合”
将编号分别为1…N的N个对象划分为不相交集合,
在每个集合中,选择其中某个元素代表所在集合。
常见两种操作:
合并两个集合
查找某元素属于哪个集合
所以,也称为“并查集”
实现方法(1)
用编号最小的元素标记所在集合;
定义一个数组 set[1..n] ,其中set[i] 表示元素i 所在的集合;
1
2
3
4
5
6
7
8
9
10
1
2
1
4
2
6
1
6
2
2
i
Set(i)
不相交集合: {1,3,7}, {4}, {2,5,9,10}, {6,8}
方法(1)——效率分析
find1(x)
{
return set[x];
}
Merge1(a,b)
{ i = min(a,b);
j = max(a,b);
for (k=1; k<=N; k++) {
if (set[k] == j)
set[k] = i;
}
}
Θ(1)
Θ(N)
有待改进?
对于“合并操作”,必须搜索全部元素!
树结构如何?
实现方法(2)
每个集合用一棵“有根树”表示
定义数组 set[1..n]
set[i] = i , 则i表示本集合,并是集合对应树的根
set[i] = j, j<>i, 则 j 是 i 的父节点.
1
2
3
4
5
6
7
8
9
10
1
2
3
2
1
3
4
3
3
4
i
Set(i)
1
5
2
4
7
10
3
6
8
9
方法(2)——效率分析
find2(x)
{
r = x;
while (set[r] != r)
r = set[r];
return r;
}
merge2(a, b)
{
set[a] = b;
}
Θ(1)
最坏情况Θ(N)
一般情况是…?
困惑~~~
性能有本质改进?
如何避免最坏情况?