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 Classication
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 uV, Adj[u] stores us neighbors, i.e. {vV | (u, v)E}
v - just outgoing edges if directed
b
Adj
Figure 1: Adjacency Lists
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
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
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
vV
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)
Lecture 13
Searching II
6.006 Spring 2008
Depth-First Search (DFS):
This is like exploring a maze.
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
Lecture 13
Searching II
6.006 Spring 2008
Example:
S1
forward
edge
back
edge
cross edge
S2
6
back edge
Figure 6: Depth-First Traversal
Edge Classication:
tree edges (formed by parent)
nontree edges
back edge: to ancestor
forward edge: to descendant
cross edge (to another subtree)
Figure 7: Edge Classication
To compute this classication, 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)
sV
DFS outer loop adds just O(V )
= O(V + E) time (linear time)
