Breadth-First Search For each vertex u, we keep the data ucolor: black/white/gray u distance: distance from s to u. upred: predecessor of u Q: a First-in-First-out queue to keep those vertices that we need"to check them later on Start by putting So remove s So remove r So remove w So remove y s into Q from O and from Q and from O and from O and check its white check its white check its white 'check its white neighbors neighbors neighbors ne eight bors Qs Qrw Qw Qvt x 002009 ②a∞②62262 v vwxyvwxyvwXyvwxy Looking at Q: Looking at Q: Looking at Q: Looking at Q: Looking at Q the first node to the first node to the first node to the first node to the first node to check is s check is r check is check is v heck is t City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-16
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 - 16 Breadth-First Search For each vertex u, we keep the data: u.color: black/white/gray u.distance: distance from s to u. u.pred: predecessor of u Q : a First-in-First-out queue to keep those vertices that we need “to check them later on” 0 r s t u v w x y 1 0 1 r s t u v w x y 1 0 2 1 r s t u v w x y 1 0 2 1 2 2 r s t u v w x y 1 0 2 1 2 2 r s t u v w x y Q s Q r w Q w v Q v t x Q t x Start by putting s into Q, So remove s from Q and check its white neighbors So remove r from Q and check its white neighbors So remove w from Q and check its white neighbors So remove v from Q and ‘check its white neighbors’ Looking at Q: the first node to check is s: Looking at Q: the first node to check is r Looking at Q: the first node to check is w Looking at Q: the first node to check is v Looking at Q: the first node to check is t
Breadth-First Search For each vertex u, we keep the data ucolor: black/white/gray u distance: distance from s to u. upred: predecessor of u Q: a First-in-First-out queue to keep those vertices that we need "to check them later on So remove y So remove t So remove x So remove u So remove y from O and from Q and from Q and from Q and from Q and check its white check its white check its white check its white check its white neighbors neighbors neighbors neighbo ors neighbors X Qxul 0080099909900,090月0 02202203②0232023 v wxy WXy vwxy vwXyvwxy Looking at Q ooking at Q: Looking at Q: Looking at Q: Looking at Q the first node to the first node to the first node to the first node to no more nodes check is t check is x check is u heck is y to check=> End City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-17
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 - 17 Breadth-First Search For each vertex u, we keep the data: u.color: black/white/gray u.distance: distance from s to u. u.pred: predecessor of u Q : a First-in-First-out queue to keep those vertices that we need “to check them later on” 1 0 2 1 2 2 r s t u v w x y Q t x So remove v from Q and ‘check its white neighbors’ Looking at Q: the first node to check is t 1 0 2 1 2 3 2 r s t u v w x y Q x u So remove t from Q and check its white neighbors Looking at Q: the first node to check is x 1 0 2 1 2 3 2 3 r s t u v w x y Q u y So remove x from Q and check its white neighbors Looking at Q: the first node to check is u 1 0 2 1 2 3 2 3 r s t u v w x y Q y So remove u from Q and ‘check its white neighbors’ Looking at Q: the first node to check is y 1 0 2 1 2 3 2 3 r s t u v w x y Q So remove y from Q and ‘check its white neighbors’ Looking at Q: no more nodes to check=> End
Breadth-First Search BFS(G, S)/*G=(V,E)* The running For each vertex u in V-S) time of BFS is: u. color= white u. distance=oo ⊙(V) O(V+E) u pred= NIL S color- gray 6 s distance=0 7 S pred=NIL 9 ENQUEUE(Q,S 10 while o≠ 1 u=DEQUEUEQQ) 2 for each v adjacent to u Total number of edges 13 if v color= white kept by the adjacency list 14 Ⅴ color=gray is⊙(E 15 vdistance =u distance Total time spent in the 16 v pred =u adjacency list is O(E) 17 ENQUEUE(Q V) 18 u color= black
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 - 18 Breadth-First Search BFS(G,s) /*G=(V,E)*/ 1 For each vertex u in V - {s} 2 u.color = white 3 u.distance = 4 u.pred = NIL 5 s.color = gray 6 s.distance = 0 7 s.pred = NIL 8 Q = 9 ENQUEUE(Q,s) 10 while Q 11 u = DEQUEUE(Q) 12 for each v adjacent to u 13 if v.color = white 14 v.color = gray 15 v.distance = u.distance + 1 16 v.pred = u 17 ENQUEUE(Q,v) 18 u.color = black (V) Total number of edges kept by the adjacency list is (E) Total time spent in the adjacency list is O(E) The running time of BFS is: O(V+E)
Breadth-First Search PRINT-PATH(G, S, v) / print the shortest path from s to v * 1 ifV=s pI else v pI print no path froms tov"exists else PRINT-PATH(G, S, vpred) print 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-19
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 - 19 Breadth-First Search PRINT-PATH(G,s,v) /* print the shortest path from s to v */ 1 if v = s 2 print s 3 else 4 if v.pred = NIL 5 print “no path from” s “to” v “exists” 6 else 7 PRINT-PATH(G, s, v.pred) 8 print v
Depth-First Search Depth-First Search(BFS DFS(G/G=(V,E)*/ The running 1 for each vertex u in v time of DFS Explores the edges of ⊙() a graph by searching 2 u color= white is: O(V+E) deeper"whenever 3 u pred= NIL ⊙)+ possible 4 for each vertex u in v Time to if u color= white execute calls to DFS-VISIT(u) DES- VISIT DFS-VISiT(u) X ucolor=gray 2 for each v adjacent to u Total number of edges kept by 3 ify color= white he adjacency v pred=u sts⊙日E Total time spent 5 in the adjacency X DFS-VISIT(v) 6 ucolor= black sts⊙ 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-20
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 - 20 Depth-First Search Explores the edges of a graph by searching “deeper” whenever possible. Depth-First Search (BFS) u v w x y z u v w x y z DFS(G) /*G = (V,E) */ 1 for each vertex u in V 2 u.color = white 3 u.pred = NIL 4 for each vertex u in V 5 if u.color = white 6 DFS-VISIT(u) DFS-VISIT(u) 1 u.color = gray 2 for each v adjacent to u 3 if v.color = white 4 v.pred = u 5 DFS-VISIT(v) 6 u.color = black (V) (V) + Time to execute calls to DFS-VISIT Total number of edges kept by the adjacency list is (E). Total time spent in the adjacency list is (E). The running time of DFS is: (V+E)