The Disjoint Set ADT In this part,we describe an efficient data structure to solve the eguivalence problem. ■ Relations:A relation R is defined on a set Sif for every pair of elements (a,b),a,bes,a Rb is either true or false.If a R b is true,then we say that a is related to 6
The Disjoint Set ADT ◼ In this part, we describe an efficient data structure to solve the equivalence problem. ◼ 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
The Disjoint Set ADT Equivalence Relations:An equivalence relation is a relation R that satisfies three properties: Reflexive:a R a,for all aeS; Symmetric:a R b if and only if b R a; Transitive:a R b and b R cimplies that a R c The relationship is not an equivalence relationship. Two cities are related if they are in the same country.This relation is an equivalence relation if all the roads are two-way
The Disjoint Set ADT ◼ Equivalence Relations: An equivalence relation is a relation R that satisfies three properties: ✓ Reflexive: a R a, for all aS; ✓ Symmetric: a R b if and only if b R a; ✓ Transitive: a R b and b R c implies that a R c; ◼ The relationship is not an equivalence relationship. ◼ Two cities are related if they are in the same country. This relation is an equivalence relation if all the roads are two-way
The Disjoint Set ADT Given an equivalence relation ~the natural problem is to decide,for any a and b,if ab. The equivalence class of an element aeSis the subset of S that contains all the elements that are related to a. Notice that the equivalence classes from a partition of S:Every member of S appears in exactly one equivalence class
The Disjoint Set ADT ◼ Given an equivalence relation ~, the natural problem is to decide, for any a and b, if a~b. ◼ The equivalence class of an element aS is the subset of S that contains all the elements that are related to a. ◼ Notice that the equivalence classes from a partition of S: Every member of S appears in exactly one equivalence class
The Disjoint Set ADT To decide if ab,we need only to check whether a and b are in the same equivalence class.This provides our strategy to solve the equivalence problem. The input is initially a collection of Nsets,each with one element.Each set has a different element. There are two permissible operations
The Disjoint Set ADT ◼ To decide if a~b, we need only to check whether a and b are in the same equivalence class. This provides our strategy to solve the equivalence problem. ◼ The input is initially a collection of N sets, each with one element. Each set has a different element. ◼ There are two permissible operations
The Disjoint Set ADT The first is Find,which returns the name of the set (that is,the equivalence class)containing a given element. The second operation adds relations.If we want to add the relation a~b,then we first see if a and b are already related.This is done by performing Findson both a and b and checking whether they are in the same equivalence class. If they are not,then we apply Union.This operation merges the two equivalence classes containing a and b into a new equivalence class
The Disjoint Set ADT ◼ The first is Find, which returns the name of the set (that is, the equivalence class) containing a given element. ◼ The second operation adds relations. If we want to add the relation a~b, then ✓ we first see if a and b are already related. This is done by performing Finds on both a and b and checking whether they are in the same equivalence class. ✓ If they are not, then we apply Union. This operation merges the two equivalence classes containing a and b into a new equivalence class