Disjoint Sets The Disjoint Set data structure e Maintains a collection of disjoint sets o Each set has a representative member e Supports the following operations MAKE-SET(X): creates a new set containing X {x} x is also the representative 0y9·j UNION(x,y): unites the sets that contain x and y a X。V FIND-SET(x): returns a pointer to the representative of the set containing x Takes o(1) if each element has a pointer pointing to the representative CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-11
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 11 Disjoint Sets The Disjoint Set data structure Maintains a collection of disjoint sets. {.,a,..} {.,y,..} {.,q,..} {.,a,..} {.,y,..} {.,q,..} {x} {.,a,..} {.,q,..} {..x,y,..} {.,a,..} {.,q,..} {..x,y,..} FIND-SET(x): returns a pointer to the representative of the set containing x. Each set has a representative member. Supports the following operations: MAKE-SET(x): creates a new set containing x. x is also the representative. UNION(x,y): unites the sets that contain x and y. Takes O(1) if each element has a pointer pointing to the representative
Representation of Graphs Example of graph Standard representation methods G=(V, E V={1,v2V3-} 1. Adjacency-matrix 2. Adjacency-list E=4)22)/3)4123/a+1man an edge connects 4 Directed graph 2|000 v to v. 30000 4|0100c 5000104 5 256246 6000001 Undirected graph Quick to find edges Compact size Usually used for Usually used for No loop dense graphs sparse graphs (E|<< 1,v2)=(v2,V1) City Univ of HK / Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-12
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 12 Representation of Graphs Standard representation methods: a 1 2 3 4 5 6 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 5 0 0 0 0 0 0 6 0 0 0 0 0 0 1. Adjacency-matrix 2. Adjacency-list • Compact size • Usually used for sparse graphs (|E| << |V|2 ) • Quick to find edges • Usually used for dense graphs 1 2 3 4 5 6 Example of graph: G = (V,E) V = {v1 ,v2 ,v3 ..} E = {(v1 ,v2 ),(v2 ,v3 ),(v3 ,v1 )..} Undirected graph 1 2 3 4 5 6 Directed graph • No loop • (v1 ,v2 ) = (v2 ,v1 ) 1 1 1 1 1 1 1 1 6 5 4 3 2 1 2 4 / 5 / 6 5 / 2 / 4 / 6 / a1,2=1 means an edge connects v1 to v2
Representation of Graphs 1. Adjacency-matrix 2. Adjacency-list Memory requirement: memory requirement ⊙NVP,or⊙(2) ⊙(V+ED,or⊙+E) 123456 Directed 010100 graph 2000010 5 3|000011 3+65 4010000 4-2 5000100 6|00000 6L十6 123456123456 Undirected 010100 graph 21001 Don't 3000011300 Care 16+57 41100104110 0111005011 6001000600000 63 CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-13
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 13 Representation of Graphs Undirected graph 1 2 3 4 5 6 1 2 3 4 5 6 Directed graph 1. Adjacency-matrix 2. Adjacency-list 6 5 4 3 2 1 2 4 / 5 / 6 5 / 2 / 4 / 6 0 0 0 0 0 0 6 / 5 0 0 0 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 3 4 5 6 6 0 0 0 0 0 0 5 0 0 0 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Memory requirement: (|V|2 ), or (V2 ) Memory requirement: (|V|+|E|), or (V+E) 6 0 0 0 0 0 0 5 0 0 0 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 3 4 5 6 6 0 0 0 0 0 0 5 0 0 0 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 0 0 0 0 0 0 5 0 0 0 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 3 4 5 6 6 0 0 0 0 0 5 0 0 0 0 0 4 0 0 0 0 0 3 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Don’t Care 6 5 4 3 2 1 2 4 / 6 5 / 5 1 / 4 / 5 1 / 2 / 4 2 / 3 / 3 / 1 1 1 1 1
Breadth-First Search Breadth-First Search(BFS Explores the edges of a graph to reach every vertex from a vertex s, with"shortest paths"Wxy VWy d n The algorithm For r, we do the for w, we do the Start by inspecting So we connect same to its white same to its white the source vertex s them color neighbors: color neighbors 58 st u vwx y vwx y vwx y vwx y For s, its 2 neighbors Now r and w join Now v joins Now t and x join are not yet searched our solution our solution our solution CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-14
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 14 Breadth-First Search Explores the edges of a graph to reach every vertex from a vertex s, with “shortest paths” r s t u v w x y r s t u v w x y s r u t w v y x r s t u v w x y So we connect them: The algorithm: Start by inspecting the source vertex S: r s t u v w x y r s t u v w x y For r, we do the same to its white color neighbors: For s, its 2 neighbors are not yet searched Now r and w join our solution r s t u v w x y For w, we do the same to its white color neighbors: Breadth-First Search (BFS) Now v joins our solution Now t and x join our solution …
Breadth-First Search Using 3 colors: white/ gray black For r, we do the for w we do the Start by inspecting So we connect same to its white same to its white the source vertex s them color neighbors: color neighbors W X V W v wXy vwxy For s, its 2 neighbors Now r and w join Now v joins Now t and x join are not yet searched our solution our solution our solution No more need to No more need to No more need to Since s is in our check s, so mark it check r so mark it check w so mark it solution, and it is to black black black be inspected, we r and w join our v joins our solution, t and x join our mark it gray solution, we need to we need to check it solution. we need to check them later on. later on. so mark it check them later on CS3381 Des Anal of Alg(2001-2002 so mark them gray. gray so mark them gray City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms -15
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 15 Breadth-First Search r s t u v w x y So we connect them: Using 3 colors: white / gray / black Start by inspecting the source vertex S: r s t u v w x y r s t u v w x y For r, we do the same to its white color neighbors: For s, its 2 neighbors are not yet searched Now r and w join our solution r s t u v w x y For w, we do the same to its white color neighbors: Now v joins our solution Now t and x join our solution … Since s is in our solution, and it is to be inspected, we mark it gray No more need to check s, so mark it black. r and w join our solution, we need to check them later on, so mark them gray. No more need to check r, so mark it black. v joins our solution, we need to check it later on, so mark it gray. No more need to check w, so mark it black. t and x join our solution, we need to check them later on, so mark them gray