# 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
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){
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
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