Tutorial: https://www.youtube.com/watch?v=UBY4sF86KEY (10 mins)
Output:
Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b
Item b is in the set D
{a=a, b=d, c=c, d=d, e=e}
{a=1, b=1, c=1, d=2, e=1}
Rank of d is greater than that of e
Setting the parent of e to d
Item e is in the set D
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}
Item a is in the set A
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}
Both a and e have same Ranks
Setting the parent of e to a
Update rank of a by child e
Rank of a is greater than that of l
Setting the parent of l to a
Rank of a is greater than that of i
Setting the parent of i to a
Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b
Both d and a have same Ranks
Setting the parent of a to d
Update rank of d by child a
{a=d, b=d, d=d, e=a, i=a, l=a}
{a=2, b=1, d=3, e=1, i=1, l=1}
Java Implementation (Without Union by Rank and Path Compression):
import java.util.*; public class DisjointSets { private static Map<Character, Character> PARENT; public static void initialize(char[] universe){ PARENT = new HashMap<>(); for(char x:universe){ PARENT.put(x, x); } } public static char Find(char item){ char parent = PARENT.get(item); if(parent==item)return item; else return Find(parent); } public static void Union(char setA, char setB){ PARENT.put(PARENT.get(setA), setB); } public static void main(String[] args) throws Exception{ char universe[] = {'a', 'b', 'c', 'd', 'e'}; initialize(universe); //Set parent of d to b Union('d', 'b'); System.out.println("Item d is in the set "+Character.toUpperCase(Find('d'))); //Set parent of b to e Union('b', 'e'); System.out.println("Item d is in the set "+Character.toUpperCase(Find('d'))); } }
Output:
Item d is in the set B
Item d is in the set E
Implementation With Union By Rank (attach lesser rank node to greater one) and Path Compression (Union of roots):
import java.util.*; public class DisjointSetsUnionByRankPathCompression{ private static Map<Character, Character> PARENT; private static Map<Character, Integer> RANKS; //to store the depths public static void initialize(char[] universe){ PARENT = new HashMap<>(); RANKS = new HashMap<>(); for(char x:universe){ PARENT.put(x, x); RANKS.put(x, 1); } } public static char Find(char item){ char parent = PARENT.get(item); // System.out.println("Finding the parent of "+item+" is: "+parent); if(parent==item)return item; else return Find(parent); } public static void Union(char setA, char setB){ char pA, pB; while((pA = PARENT.get(setA))!=setA){setA = pA;} while((pB = PARENT.get(setB))!=setB){setB = pB;} int rankFirst = RANKS.get(setA), rankSecond = RANKS.get(setB); if(rankFirst>rankSecond){ PARENT.put(setB, setA); System.out.println("\nRank of "+setA+" is greater than that of "+setB); System.out.println("Setting the parent of "+setB+" to "+setA); updateRanksUpward(setB); }else if(rankSecond>rankFirst){ PARENT.put(setA, setB); System.out.println("\nRank of "+setB+" is greater than that of "+setA); System.out.println("Setting the parent of "+setA+" to "+setB); updateRanksUpward(setA); }else{ PARENT.put(setB, setA); System.out.println("\nBoth "+setA+" and "+setB+" have same Ranks"); System.out.println("Setting the parent of "+setB+" to "+setA); updateRanksUpward(setB); } } public static void updateRanksUpward(char current){ int currentDepth = RANKS.get(current); char currentsParent = PARENT.get(current); int parentsDepth = RANKS.get(currentsParent); if(!(currentDepth<parentsDepth || currentsParent == current)){ System.out.println("Update rank of "+currentsParent+" by child "+current); RANKS.put(currentsParent, currentDepth+1); updateRanksUpward(currentsParent); } } public static void main(String[] args) throws Exception{ char universe[] = {'a', 'b', 'c', 'd', 'e'}; initialize(universe); //Set parent of d to b Union('d', 'b'); System.out.println("Item b is in the set "+Character.toUpperCase(Find('b'))); System.out.println(PARENT); System.out.println(RANKS); //Set parent of b to e Union('b', 'e'); System.out.println("Item e is in the set "+Character.toUpperCase(Find('e'))); System.out.println(PARENT); System.out.println(RANKS); //Find the set of a System.out.println("Item a is in the set "+Character.toUpperCase(Find('a'))); System.out.println(PARENT); System.out.println(RANKS); //Test 2 initialize(new char[]{'a','e','l','i','d','b','e'}); Union('a', 'e'); Union('e', 'l'); Union('l', 'i'); Union('d', 'b'); Union('b', 'e'); //(Unite the two sets that is union(a, d) - unite both sets System.out.println(PARENT); System.out.println(RANKS); } }
Output:
Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b
Item b is in the set D
{a=a, b=d, c=c, d=d, e=e}
{a=1, b=1, c=1, d=2, e=1}
Rank of d is greater than that of e
Setting the parent of e to d
Item e is in the set D
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}
Item a is in the set A
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}
Both a and e have same Ranks
Setting the parent of e to a
Update rank of a by child e
Rank of a is greater than that of l
Setting the parent of l to a
Rank of a is greater than that of i
Setting the parent of i to a
Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b
Both d and a have same Ranks
Setting the parent of a to d
Update rank of d by child a
{a=d, b=d, d=d, e=a, i=a, l=a}
{a=2, b=1, d=3, e=1, i=1, l=1}
No comments:
Post a Comment