下标0123456789 parent-44-32-320004 集合S1,S2和S3的双亲表示 ② 6⑦8①⑨③⑤
6 S1 下标 parent 集合 S1 , S2 和 S3 的双亲表示 -4 4 -3 2 -3 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 6 7 8 4 1 9 2 3 5 S2 S3
下标0123456789 parent-74|-32020004 合S1∪S,和S3的双亲表示 6⑦⑧④ S1∪S2的可能的表示方法
7 S1 S2的可能的表示方法 下标 parent 集合 S1 S2和 S3的双亲表示 -7 4 -3 2 0 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 6 7 8 4 1 9 4 0 1 9 6 7 8
并查集的结构定义 const int setsize=50;并查集元素个数 typedef struct i )并查集结构定义 int parent[ Setsize;/合元素数组 3 UFSets; void InitufSets( UFSets*S){∥集合初始化 for( int i=0; i< Setsize; 1++) S->parent[1=-1 //每一个自成一个单元素集合
8 并查集的结构定义 const int SetSize = 50; //并查集元素个数 typedef struct { //并查集结构定义 int parent[SetSize]; //集合元素数组 } UFSets; void InitUFSets (UFSets *S) { //集合初始化 for ( int i = 0; i < SetSize; i++ ) S->parent[i] = -1; } //每一个自成一个单元素集合
A并查集操作的算法 查找 5 0 ((23 Find(s, 4) Find (s, 3)=3 Find(s, 2)=2 Find(s,1)=1 Find(s, 0)=0 5<0结束
9 并查集操作的算法 ◼ 查找 -5 0 1 2 3 0 1 2 3 4 Find (S,4) Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1 Find (S,0) = 0 = -5 < 0 结束
0 2 3 parent 50123 Parent!0l Parent] 5 Parent[1] Parent(3=3 =0 Parent2=2 int Find(UFSets *S, int x)& if(s->parent [x]<0)return x else return Find(S,S->parent [x]);
10 int Find (UFSets * S, int x ) { if ( S->parent [x] < 0 ) return x; else return Find (S, S->parent [x] ); } parent -5 0 1 2 3 Parent[4] Parent[3] =3 Parent[2] =2 =1 Parent[1] =0 Parent[0] =-5 0 1 2 3 4