DOC PREVIEW
MIT 6 006 - Breadth-First Search and Depth-First Search

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MIT OpenCourseWare http://ocw.mit.edu6.006 Introduction to AlgorithmsSpring 2008For 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 Classification Readings CLRS 22.2-22.3 Recall: graph search: explore a graph e.g., find 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 abcabcccbaAdjFigure 1: Adjacency Lists 1Lecture 13 Searching II 6.006 Spring 2008 . . .level Øslevel 1level 2last levelFigure 2: Breadth-First Search Breadth-first 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] � previous level, i − 1 while frontier: next = [ ] � next level, i for u in frontier: for v in Adj [u]: if v not in level: � not yet seen level[v] = i � = level[u] + 1 parent[v] = u next.append(v) frontier = next i + = 1 2� � Lecture 13 Searching II 6.006 Spring 2008 Example: asdfvcxz1Ø233221level Ølevel 1level 2level 3frontierØ = {s}frontier1 = {a, x}frontier2 = {z, d, c}frontier3 = {f, v}(not x, c, d)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 • ⇒ time = � Adj[V ] = | E | for directed graphs v�V | |2 | E | for undirected graphs • 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 find shortest path, take v, parent[v], parent[parent[v]], etc., until s (or None) ⇒ 3Lecture 13 Searching II 6.006 Spring 2008 Depth-First Search (DFS): This is like exploring a maze. sFigure 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: 1326back edge7548back edgeforward edgecross edgeabcdefS1S2Figure 6: Depth-First Traversal Edge Classification: back edge: to ancestorforward edge: to descendantcross edge (to another subtree)tree edges (formed by parent)nontree edgesFigure 7: Edge Classification To compute this classification, 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) ⇒


View Full Document

MIT 6 006 - Breadth-First Search and Depth-First Search

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Breadth-First Search and Depth-First Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Breadth-First Search and Depth-First Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Breadth-First Search and Depth-First Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?