Disjoint Set ADT notes - data structure Mr. Zhong Hong

Mango harden 2022-01-15 01:38:02

One . Equivalence relation

1. aggregate S Relationship on R If it's symmetrical 、 Reflexive 、 Transitive , Just say R yes S An equivalent relation on

application : The connectivity of a graph is an equivalent relation

2. Flexible equivalence relation problems and equivalence classes

give S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } and 9 An equivalence relation 124, 31, 610, 89, 74, 68, 35, 211, 1112

Judge S Whether any two elements in are equivalent

Ideas : Find the equivalence class , If these two elements belong to the same equivalence class , Then it's equivalent

Equivalence class { 2, 4, 7, 11, 12 }, { 1, 3, 5 }, { 6, 8, 9, 10 }

The pseudocode is as follows

Algorithm: Union/Find
{
/* The first step is to read in the relationship */
initinalize N disjoint relations
while (read in a~b){
if (!Find(a)==Find(b))
Union the two sets;
}
/* The second step is to judge whether a~b*/
while (read in a and b){
if (Find(a)==Find(b))
output(true)
else output(false)
}
}

Next, we mainly analyze union and find operation  

Two . Basic data structure

Using a tree like structure to represent equivalence classes

S1={6,7,8,10}

Union(i,j)  Merge Si and Sj, It's really just the Sj( or Si) Receive Si To become Si The subtree of

Realization : Definition int Array S[1,2,3....N]   S[element]=root   S[root]=0

typedef int *DisjSet
typedef int ElementType
typedef int SetType
void SetUnion ( DisjSet S, SetType Rt1, SetType Rt2 )
{ S [ Rt2 ] = Rt1 ; }
SetType Find(ElementType X, DisjSet S){
for (;S[X]>0;X=S[X])
return X;
}

Textbook Find It's recursion

SetType Find(ElementType X,DisjSet S){
if (S[X]<=0)
return X;
else
return Find(S[X],S);
}

This direct union The operation of may produce O(N^2) Of bad case

Let's discuss two optimization methods union Algorithm

3、 ... and .union Optimization algorithm

1.Union by size

Always change the smaller tree , Make it a sub tree of a larger tree

here S[root] No longer initialized to 0, Instead, initialize to -1, Every time you add a new element, subtract -1

Final S[root]=-size

void SetUnion(DisjSet S, SetType Root1, SetType Root2){
if (S[Root1]>S[Root2]){
S[Root2]+=S[Root1];
S[Root1]=Root2;
}
else{ // Wait for height to change root2
S[Root1]+=S[Root2];
S[Root2]=Root1;
}
}

 Time complexity of  N  Union and M Find operations is now O( N + M log2 N )

2.Union by height

Always change the shallower tree , Make it a subtree of the higher tree

here S[root] Can still be initialized to 0, Final S[root]=-height

void SetUnion(DisjSet S, SetType Root1, SetType Root2){
if (S[Root1]>S[Root2]){
S[Root1]=Root2;
}
else{
if (S[Root1]==S[Root2])
S[Root1]--;
S[Root2]=Root1;
}
}

3.Path compression

Path compression in Find In operation , And Union irrelevant . If the operation is Find(X), here find The effect is from X Each node on the path to the root makes its parent node a root

SetType Find(ElementType X, DisjSet S){
int root,trail,lead;
for (root=X;Set(root)>0;root=S[root]);
for (trail=X;trail!=root;trail=lead){ //S[trail] Will change , So use lead Retain S[trail] Value
lead=S[trail];
S[trail]=root;
}
return root;
}

Be careful : Path compression is not associated with union by height compatible , Because the height of the tree changes when the path is compressed . The program questions in our homework are also used union by size And uses the operation of path compression

Four . Homework

Judge the connectivity of undirected graphs

The routine is as follows , I hope to have a special assignment before the end of the term , Write your homework in detail , Think of it as a review

 


thank
Similar articles

2022-01-15

***

2022-01-15

***

2022-01-15

***

2022-01-15

2022-01-15

2022-01-15

2022-01-15