Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 29, 2009 11:37:05 PM!dynamic connectivity!quick find!quick union!improvements!applicationsUnion-Find AlgorithmsSteps to developing a usable algorithm.•Model the problem.•Find an algorithm to solve it.•Fast enough? Fits in memory?•If not, figure out why.•Find a way to address the problem.•Iterate until satisfied.The scientific method.Mathematical analysis.2Subtext of today’s lecture (and this course)3!dynamic connectivity!quick find!quick union!improvements!applicationsGiven a set of objects•Union: connect two objects.•Find: is there a path connecting the two objects?4Dynamic connectivity6 51487320union(3, 4)union(8, 0)union(2, 3)union(5, 6) find(0, 2) no find(2, 4) yesunion(5, 1)union(7, 3)union(1, 6) find(0, 2) yes find(2, 4) yesunion(4, 8)more difficult problem: find the path5Network connectivity: larger examplepqDynamic connectivity applications involve manipulating objects of all types.•Variable name aliases.•Pixels in a digital photo.•Computers in a network.•Web pages on the Internet.•Transistors in a computer chip.•Metallic sites in a composite system.When programming, convenient to name objects 0 to N-1.•Use integers as array index.•Suppress details not relevant to union-find.6Modeling the objectscan use symbol table to translate from object names to integers (stay tuned)Transitivity.If p is connected to q and q is connected to r, then p is connected to r.Connected components. Maximal set of objects that are mutually connected.7Modeling the connections6 51487320{ 1 5 6 } { 2 3 4 7 } { 0 8 }connected componentsFind query. Check if two objects are in the same set.Union command. Replace sets containing two objects with their union.8Implementing the operations6 51487320{ 1 5 6 } { 2 3 4 7 } { 0 8 }6 517320{ 1 5 6 } { 0 2 3 4 7 8 }48union(4, 8)connected components9Goal. Design efficient data structure for union-find.•Number of objects N can be huge. •Number of operations M can be huge.•Find queries and union commands may be intermixed.Union-find data type (API) public class UnionFind public class UnionFindUnionFind(int N)create union-find data structure withN objects and no connectionsbooleanfind(int p, int q)are p and q in the same set?voidunite(int p, int q)replace sets containing p and qwith their union10!dynamic connectivity!quick find!quick union!improvements!applications11Data structure.•Integer array id[] of size N.•Interpretation: p and q are connected if they have the same id. i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 9 9 6 6 7 8 95 and 6 are connected2, 3, 4, and 9 are connectedQuick-find [eager approach]0 12345 678912Data structure.•Integer array id[] of size N.•Interpretation: p and q are connected if they have the same id.Find. Check if p and q have the same id. i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 9 9 6 6 7 8 9id[3] = 9; id[6] = 63 and 6 not connectedQuick-find [eager approach]5 and 6 are connected2, 3, 4, and 9 are connected13Data structure.•Integer array id[] of size N.•Interpretation: p and q are connected if they have the same id.Find. Check if p and q have the same id.Union. To merge sets containing p and q, change all entries with id[p] to id[q]. i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 9 9 6 6 7 8 9union of 3 and 62, 3, 4, 5, 6, and 9 are connected i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 6 6 6 6 6 7 8 6id[3] = 9; id[6] = 63 and 6 not connectedproblem: many values can changeQuick-find [eager approach]5 and 6 are connected2, 3, 4, and 9 are connected143-4 0 1 2 4 4 5 6 7 8 9 4-9 0 1 2 9 9 5 6 7 8 9 8-0 0 1 2 9 9 5 6 7 0 9 2-3 0 1 9 9 9 5 6 7 0 9 5-6 0 1 9 9 9 6 6 7 0 9 5-9 0 1 9 9 9 9 9 7 0 9 7-3 0 1 9 9 9 9 9 9 0 9 4-8 0 1 0 0 0 0 0 0 0 0 6-1 1 1 1 1 1 1 1 1 1 1 Quick-find exampleproblem: many values can changepublic class QuickFind{ private int[] id; public QuickFind(int N) { id = new int[N]; for (int i = 0; i < N; i++) id[i] = i; } public boolean find(int p, int q) { return id[p] == id[q]; } public void unite(int p, int q) { int pid = id[p]; for (int i = 0; i < id.length; i++) if (id[i] == pid) id[i] = id[q]; }}15check if p and q have same id (1 operation)change all entries with id[p] to id[q](N operations)set id of each object to itself(N operations)Quick-find: Java implementationQuick-find defect.•Union too expensive (N operations).•Trees are flat, but too expensive to keep them flat.Ex. May take N2 operations to process N union commands on N objects.16Quick-find is too slowalgorithmunionfindquick-findN 1Rough standard (for now).•109 operations per second.•109 words of main memory.•Touch all words in approximately 1 second.Ex. Huge problem for quick-find.•109 union commands on 109 objects.•Quick-find takes more than 1018 operations.•30+ years of computer time!Paradoxically, quadratic algorithms get worse with newer equipment.•New computer may be 10x as fast.•But, has 10x as much memory so problem may be 10x bigger.•With quadratic algorithm, takes 10x as long!17a truism (roughly) since 1950 !Quadratic algorithms do not scale18!dynamic connectivity!quick find!quick union!improvements!applications19Data structure.•Integer array id[] of size N.•Interpretation: id[i] is parent of i.•Root of i is id[id[id[...id[i]...]]].Quick-union [lazy approach]keep going until it doesn’t change i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 4 9 6 6 7 8 93's root is 9; 5's root is 6354270 1 9 6 8pqData structure.•Integer array id[] of size N.•Interpretation: id[i] is parent of i.•Root of i is id[id[id[...id[i]...]]].Find. Check if p and q have the same root.354270 1 9 6 820 i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 4 9 6 6 7 8 93's root is 9; 5's root is 63 and 5 are not connected Quick-union [lazy approach]pqkeep going until it doesn’t changeData structure.•Integer array id[] of size N.•Interpretation: id[i] is parent of i.•Root of i is id[id[id[...id[i]...]]].Find. Check if p and q have the same root.Union. To merge subsets containing p and q,set the id of q's root to the id of p's root.3 5470 1 9682354270 1 9 6 821 i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 4 9 6 6 7 8 93's root is 9; 5's root is 63 and 5 are not connected i 0 1 2 3 4 5 6 7 8 9id[i] 0 1 9 4 9 6 9 7 8
View Full Document
Unlocking...