10-05-2014, 03:09 PM
Disjoint Sets
Disjoint Sets.ppt (Size: 302.5 KB / Downloads: 69)
Equivalence Relations
A relation R is defined on a set S if for every pair of elements (a,b), a,bS, a R b is either true or false. If a R b is true, then we say that a is related to b.
An equivalence relation is a relation R that satisfy three properties:
(reflexive) a R a, for all a S.
(symmetric) a R b if and only if b R a.
(transitive) a R b and b R c implies that a R c.
Disjoint Sets
Make the input a collection of N sets, each with one element.
All relations (except reflexive) are false;
Each set has a different element: SiSj= => it makes the sets disjoint.
Find operation: returns the name of the set containing a given element.
Add/Union operation (e.g., add relation a~b)
Check if a and b are already related: if they are in the same equivalence class.
If not, apply “union”: merge the two equivalence classes containing a and b into a new equivalence class.
Example:
On a set of subsets, the three operations amount to:
Create a set of n disjoint subsets with every node in its own subset
Test whether A and B are in the same subset
If A and B are in the same subset, then do nothing, else unify the subsets to which A and B belong
Union and Find
The Union-Find problem starts with n elements (numbered 1 to n), each one representing a singleton set. We allow two operations to be performed: