广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树

§7.8.2 并查集

并查集是一种树形数据结构，用于集合的合并和查找。 并查集的主要操作有：

1）判断两个元素是否属于同一个集合 2）合并两个不相交集合 3）路径压缩

7.9.1判断两个元素是否属于同一个集合；合并两个不相交集 用S[i].father表示元素i的父亲结点 S[1].father=1

1 S[2].father=1

2 3 S[3].father=1

S[4].father=3 5 4 S[5].father=3 6 S[6].father=5

由此用某个元素所在树的根结点表示该元素所在的集合。判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样即可；

也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可

7.9.2路径压缩

如果我们每次判断两个元素是否属于同一个集合，都采用寻根判断的话，当树是链的时候，需要O(N)的时间，于是可以采用“路径压缩”的方法，提高效率。

1 1 2 3

5 4 2 3 4 5 6

6

路径压缩是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。 之后，对任意两个元素是否属于同一个集合的判断，复杂度则降为O(1)。 参考程序：

function getfather(v:integer):integer; function begin judge(x,y:integer):boolean; if (father[v]=0) var fx,fy : integer; then getfather:=v begin else begin fx := getfaher(x); father[v]:=getfather(father[v]); fy := gefather(y);

52 / 17

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程07树 getfather:=father[v]; end; end;

If fx=fy then judge := exit(true) else judge := false;

father[fx] := fy;{合并两个集合} end;

53 / 17