Question? Leave a message!




Disjoint sets

Disjoint sets
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Disjoint sets Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Disjoint sets 2 Outline In this topic, we will cover disjoint sets, including: – A review of equivalence relations – The definition of a Disjoint Set – An efficient data structure • A general tree – An optimization which results in • Worst case O(ln(n)) height • Average case O(a(n))) height • Best case Q(1) height – A few examples and applicationsDisjoint sets 3 Definitions Recall the properties of an equivalence relation: – a a for all a – a b if and only if b a – If a b and b c, it follows that a c An equivalence relation partitions a set into distinct equivalence classes Each equivalence class may be represented by a single object: the representative object – Another descriptive term for the sets in such a partition is disjoint setsDisjoint sets 4 Implicitly Defined Relations For example, big-Q defines an equivalence class of functions which grow at the same rate – We choose a single function to represent the class 2 e.g., we represent all functions with quadratic growth with n Another example: partition the numbers from 1 to 20 according to the relation a b if a and b share the same factors of 2: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 6, 10, 14, 18, 4, 12, 20, 8, 16 These equivalence relations are implicitly defined by the relationDisjoint sets 5 Explicitly Defined Disjoint Sets Alternatively, a partition or collection of disjoint sets may be used to explicitly define an equivalence relation: – a b if and only if a and b are in the same partition For example, the 10 numerals 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 can be partitioned into the three sets 1, 2, 3, 5, 7, 4, 6, 9, 0 , 8 Therefore, 1 2, 2 3, etc.Disjoint sets 6 Explicitly Defined Disjoint Sets Consider simulating a device and tracking the connected components in a circuit This forms an equivalence relation: a b if a and b are connected http://www.morphet.org.uk/ferro/s6mono.htmlDisjoint sets 7 Operations on Disjoint Sets There are two operations we would like to perform on disjoint sets: – Determine if two elements are in the same disjoint set, and – Take the union of two disjoint sets creating a single set We will determine if two objects are in the same disjoint set by defining a function which finds the representative object of one of the disjoint sets – If the representative objects are the same, the objects are in the same disjoint setDisjoint sets 8 Implementation Given two elements a and b, they are in the same set if find( a ) == find( b ) What find returns is irrelevant so long as: – If a and b are in the same set, find( a ) == find( b ) – If a and b are not in the same set, find( a ) = find( b ) We will have find return an integerDisjoint sets 9 Implementation Here is a poor implementation: – Have two arrays and the second array stores the representative object – Finding the representative object isQ(1) – However, taking the union of two sets is Q(n) • It would be necessary to check each array entry Disjoint sets 10 Implementation As an alternate implementation, let each disjoint set be represented by a general tree – The root of the tree is the representative object To take the union of two such sets, we will simply attach one tree to the root of the other Find and union are now both O(h)Disjoint sets 11 Implementation Normally, a node points to its children: We are only interested in the root; therefore, our interest is in storing the parentDisjoint sets 12 Implementation For simplicity, we will assume we are creating disjoint sets the n integers 0, 1, 2, ..., n– 1 We will define an array parent = new size_tn; for ( int i = 0; i n; ++i ) parenti = i; If parenti == i, then i is a root node – Initially, each integer is in its own setDisjoint sets 13 Implementation We will define the function size_t Disjoint_set::find( size_t i ) const while( parenti = i ) i = parenti; T (n) = O(h) find return i; Disjoint sets 14 Implementation Initially, you will note that find( i ) = find( j ) for i = j, and therefore, we begin with each integer being in its own set We must next look at the union operation – how to join two disjoint sets into a single setDisjoint sets 15 Implementation This function is also easy to define: void set_union( size_t i, size_t j ) i = find( i ); j = find( j ); T (n) = 2T (n) + Q(1) set_union find = O(h) if ( i = j ) // slightly sub-optimal... parentj = i; The keyword union is reserved in C++Disjoint sets 16 Example Consider the following disjoint set on the ten decimal digits:Disjoint sets 17 Example If we take the union of the sets containing 1 and 3 set_union(1, 3); we perform a find on both entries and update the second Disjoint sets 18 Example Now, find(1) and find(3) will both return the integer 1Disjoint sets 19 Example Next, take the union of the sets containing 3 and 5, set_union(3, 5); we perform a find on both entries and update the second Disjoint sets 20 Example Now, if we take the union of the sets containing 5 and 7 set_union(5, 7); we update the value stored in find(7) with the value find(5):