MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms Lecture 13 Searching II 6 006 Spring 2008 Lecture 13 Searching II Breadth First Search and Depth First Search Lecture Overview Search 2 of 3 Breadth First Search Shortest Paths Depth First Search Edge Classi cation Readings CLRS 22 2 22 3 Recall graph search explore a graph e g nd a path from start vertices to a desired vertex adjacency lists array Adj of V linked lists for each vertex u V Adj u stores u s neighbors i e v V u v E v just outgoing edges if directed a b c a c b c c b Adj Figure 1 Adjacency Lists 1 a Lecture 13 Searching II 6 006 Spring 2008 s level last level level 1 level 2 Figure 2 Breadth First Search Breadth rst Search BFS See Figure 2 Explore graph level by level from S level s level i vertices reachable by path of i edges but not fewer build level i 0 from level i 1 by trying all outgoing edges but ignoring vertices from previous levels BFS V Adj s level s parent s None i 1 frontier s while frontier next for u in frontier for v in Adj u if v not in level level v i parent v u next append v frontier next i 1 2 previous level i 1 next level i not yet seen level u 1 Lecture 13 Searching II 6 006 Spring 2008 Example level level 1 1 a 2 1 z 2 s 2 x 3 d 3 c f v frontier s frontier1 a x frontier2 z d c frontier3 f v not x c d level 3 level 2 Figure 3 Breadth First Search Frontier Analysis vertex V enters next then frontier only once because level v then set base case v s Adj v looped through only once E for directed graphs time Adj V 2 E for undirected graphs v V O E time O V E to also list vertices unreachable from v those still not assigned level LINEAR TIME Shortest Paths for every vertex v fewest edges to get from s to v is level v if v assigned level else no path parent pointers form shortest path tree union of such a shortest path for each v to nd shortest path take v parent v parent parent v etc until s or None 3 Lecture 13 Searching II 6 006 Spring 2008 Depth First Search DFS This is like exploring a maze s Figure 4 Depth First Search Frontier follow path until you get stuck backtrack along breadcrumbs until reach unexplored neighbor recursively explore parent s None DFS visit V Adj s for v in Adj s if v not in parent parent v s DFS visit V Adj v DFS V Adj parent for s in V if s not in parent parent s None DFS visit V Adj s search from start vertex s only see stuff reachable from s explore entire graph could do same to extend BFS Figure 5 Depth First Search Algorithm 4 Lecture 13 Searching II 6 006 Spring 2008 Example S1 forward edge 1 a b 5 c 2 4 back edge 8 d 3 cross edge S2 6 f e 7 back edge Figure 6 Depth First Traversal Edge Classi cation tree edges formed by parent nontree edges back edge to ancestor forward edge to descendant cross edge to another subtree Figure 7 Edge Classi cation To compute this classi cation keep global time counter and store time interval during which each vertex is on recursion stack Analysis DFS visit gets called with a vertex s only once because then parent s set time in DFS visit Adj s O E s V DFS outer loop adds just O V O V E time linear time 5
View Full Document
Unlocking...