Disjoint set / Union Find Data Structure

This Slide explains about the Disjoint Set Data Structure. Its a part of Course Data Structure - Part 2 which is published on Udemy.

You can find its explanation video on Udemy.
Link: https://www.udemy.com/logn-data-structure-part2/

YouTube Channel Name: Logn Research Group

1. Disjoint/Union Find Data Structure Muhammad Tariq Khan Log(n) Academy

2. Disjoint Set - Relations Topic of Discrete Mathematics Muhammad Ahmed

3. Disjoint Set - Relations Suppose we have a database of people. We want to figure out who is related to whom. Initially, we only have a list of people, and information about their relations. For example “ Muhammad is related to Ahmed ”. Further info: Muhammad is brother of Ahmed . This means that they belongs to same family. Mathematically they belong to same SET. Muhammad Ahmed

4. Disjoint Set - Relations If Muhammad is related to Ahmed, and Ahmed is related to Saam , then Muhammad is related to Saam . Once we have relationships information, we would like to answer queries like “Is Muhammad related to S aam ?” Muhammad Saam Ahmed

5. Equivalence Relations A relation R over a set S is called an Equivalence Relation if it has following properties Reflexivity: for all element x is in set S , x R x Symmetry: for all elements x and y , x R y if and only if y R x Transitivity: for all elements x , y and z , if x R y and y R z then x R z The relation “ is related to ” is an equivalence relation over the set of people. Muhammad Saam Ahmed

6. Equivalence Relations The ≤ relationship is not an equivalence relation. It is Reflexive , since x ≤ x, and Transitive , since x ≤ y and y ≤ z implies x ≤ z, it is N ot S ymmetric since x ≤ y does not imply y ≤ x.

7. Equivalence Relations - Example Electrical connectivity, where all connections are by metal wires, is an equivalence relation. It is clearly Reflexive , since any component is connected to itself. It is Symmetric because if component a is connected to component b then b must be electrically connected to a . It is T ransitive , since if component a is connected to component b and b is connected to c then a is connected to c .

8. Matrix representation of relations Jack Jamy Omar Osman Ali Jack Jamy Omar Osman Ali Jack Jamy Omar Osman Ali

9. Problem…. What if we have 1000 elements/objects/people Will this be efficient in-terms of time, space and memory to create a matrix of 1000 x 1000

10. Find & Union – Array based Approach As an example, suppose the equivalence relation is defined over the five-element set { a 1 , a 2 , a 3 , a 4 , a 5 }. There are 25 pairs of elements, each of which is related or not. (30 pairs – 5 self-pairs=25).

11. Find & Union – array based Approach However, given the information a 1 R a 2 , a 5 R a 1 , a 4 R a 2 , a 3 R a 4 , Implies that all pairs are related . We would like to be able to infer this information quickly.

12. What is Union Find Union find operation keeps track of elements which are split into one or more disjoint set. It has 2 primary operation: find and union

13. Path compression Muhammad Tariq Khan Log(n) Academy

14. How to perform Union & Find To apply Union Find, first construct a mapping between your objects and integers in the range (0, n). NOTE: This step is not necessary in general, but it will allow us to construct an array-based union find which is very efficient and easy to work with. E F A B D 0 1 2 3 4 5 6 7 H C G

15. E B A F D H C G 2 2 2 6 7 2 0 1 2 3 4 5 6 7 Instructions Find(B) = A Find(D) = A Find(H) = A Find(E) = A Indexes E F A B D 0 1 2 3 4 5 6 7 H C G

16. Union Find FIND: To find which component a particular element belongs to, first find the root of that component by following the parent nodes until a self loop is reached ( a node who’s parent is its self) UNION: To unify 2 elements find which are the root nodes of each component and if the root nodes are different make one of the root node to be the parent of the other.

17. Steps to perform union find The input is initially a collection of n sets, each with one element. This initial representation is that all relations (except reflexive relations) are false. Each set has a different element so that S i ∩ S j = null ; this makes the sets Disjoint . Find returns the name of the SET that contains a given element, i.e., S i = find( a ) Union merges two sets to create a new set S k = S i U S j .

18. Steps to perform union find If we want to add the relation a R b , then we first see if a and b are already related. This is done by performing Finds on both a and b to check whether they are in the same set. If they are not, we apply Union which merges the two sets a and b belong to. The algorithm to do this is frequently known as Union / Find for this reason. Example : Union ( D,G )

19. When and Where Disjoint set is used Kruskal’s minimum spanning tree Grid percolation Network connectivity Least Common Ancestor in tree Image processing Maze Generation

20. Union-Find Analysis Typical tree traversal not required, so no need for pointers to children, instead we need a pointer to parent – an up-tree. Union is clearly a constant time operation. Running time of find ( i ) is proportional to the height of the tree containing node i . This can be proportional to n in the worst case (but not always) Improvement: Modify Union to ensure that heights stay small.

21. Get full video course on Udemy . Course name: Data Structure – Part 2 Link : https ://www.udemy.com/logn-data-structure-part2 / For discount coupon : “ [email protected]”