Graph Traversals Depth First Search Breadth First Search 1 Depth First Search Example x y s z t w v u 2 Depth First Search Example x y z 1 s t w v u 3 Depth First Search Example x y z 1 s t 2 w v u 4 Depth First Search Example x y z 1 s t 2 3 w v u 5 Depth First Search Example x y z 1 s t 2 3 w v u 6 Depth First Search Example x y z 1 s t 2 3 4 w v u 7 Depth First Search Example x y z 1 s t 2 3 4 w 5 v u 8 Depth First Search Example x y z 1 s t 2 3 4 w 5 v u 9 Depth First Search Example x y z 1 s t 2 3 4 5 6 w v u 10 Depth First Search Example x y z 1 s t 2 7 3 4 5 6 w v u 11 Depth First Search Example x 1 y z 8 s t 2 7 3 4 5 6 w v u 12 Depth First Search Example x 1 y z 8 s t 2 7 3 4 5 6 w v u 13 Depth First Search Example x 1 y z 8 s t 9 2 7 3 4 5 6 w v u 14 Depth First Search Example x 1 y z 8 s t 9 2 7 3 4 5 6 w v u 15 Depth First Search Example x 1 y z 8 s t 2 7 9 10 3 4 5 6 w v u 16 Depth First Search Example x 1 y z 8 11 s t 2 7 9 10 3 4 5 6 w v u 17 Depth First Search Example x y 1 12 8 11 z s t 2 7 9 10 3 4 5 6 w v u 18 Depth First Search Example x y 1 12 8 11 z 13 s t 2 7 9 10 3 4 5 6 w v u 19 Depth First Search Example x y 1 12 8 11 z 13 s t 2 7 9 10 3 4 5 6 w v u 20 Depth First Search Example x y 1 12 8 11 z 13 s t 2 7 9 10 3 4 5 6 w v u 21 Depth First Search Example x y 1 12 8 11 z 13 s t 2 7 9 10 3 4 5 6 w v 14 u 22 Depth First Search Example x y 1 12 8 11 z 13 s t 2 7 9 10 3 4 5 6 w v 14 u 23 Depth First Search Example x y 1 12 8 11 z 13 s t 2 7 9 10 3 4 5 6 14 15 w v u 24 Depth First Search Example x y z 1 12 8 11 13 16 s t 2 7 9 10 3 4 5 6 14 15 w v u 25 Depth First Search Example DFS G terminated Depth first forest DFF x y z x y z 1 12 8 11 13 16 1 12 8 11 13 16 s t s t 2 7 9 10 2 7 9 10 3 4 5 6 14 15 3 4 5 6 14 15 w v u w v u 26 Depth First Search A B D C E F G Breadth First Search Sample Graph s 0 a FIFO queue Q d c 1 b a e f g just after processing vertex i h 28 Breadth First Search s 0 a 1 d FIFO queue Q e a a b c c 1 b f g just after processing vertex a i h 29 Breadth First Search s 0 a 1 d FIFO queue Q e a a b c a b c f c 1 b 2 f g i just after processing vertex a b h 30 Breadth First Search s 0 a FIFO queue Q d 1 c 1 2 b e 2 f g i a a b c a b c f a b c f e just after processing vertex a b c h 31 Breadth First Search s 0 a FIFO queue Q d 1 c 1 2 b e 2 f g i h 3 just after processing vertex a a b c a b c f a b c f e a b c f e g h a b c f 3 32 Breadth First Search s 0 a 3 FIFO queue Q 2 a a b c a b c f a b c f e a b c f e g h a b c f e g h d i d 1 c 1 b e 2 f i 3 g h 3 3 just after processing vertex a b c f e all distances are filled in after processing e 33 Breadth First Search s 0 a 3 FIFO queue Q 2 a a b c a b c f a b c f e a b c f e g h a b c f e g h d i d 1 c 1 b e 2 f i 3 g h 3 3 just after processing vertex a b c f g 34 Breadth First Search s 0 a 3 FIFO queue Q 2 a a b c a b c f a b c f e a b c f e g h a b c f e g h d i d 1 c 1 b e 2 f i 3 g h 3 3 just after processing vertex a b c f h 35 Breadth First Search s 0 a 3 FIFO queue Q 2 a a b c a b c f a b c f e a b c f e g h a b c f e g h d i d 1 c 1 b e 2 f i 3 g h 3 3 just after processing vertex a b c f d 36 Breadth First Search s 0 a 3 FIFO queue Q 2 a a b c a b c f a b c f e a b c f e g h a b c f e g h d i d 1 c 1 b e 2 f i 3 g h 3 3 just after processing vertex a b c f i algorithm terminates all vertices are processed 37 Breadth first search analysis Enqueue and Dequeue happen only once for each node O V Sum of the lengths of adjacency lists O E for a directed graph Initialization overhead O V Total runtime O V E ref Introduction to Algorithms by Thomas Cormen Depth first search analysis initialization take time O V DFS VISIT is called only once for each node since it s called only for white nodes and the first step in it is to paint the node gray the total cost of DFS VISIT it O …
View Full Document
Unlocking...