Depth-First Search
Lecture Overview
Depth-First Search
Edge Classification
Cycle Testing
Topological Sort
Recall:
graph search: explore a graph
e.g., find a path from start vertex s to a desired vertex
adjacency lists: array Adj of |V | linked lists
for each vertex u V , Adj[u] stores us neighbors, i.e., {v V | (u, v) E}
(just outgoing edges if directed)
For example:
b
Adj
Figure 1: Adjacency Lists
Breadth-first Search (BFS):
Explore level-by-level from s find shortest paths
Depth-First Search (DFS)
This is like exploring a maze.
Figure 2: Depth-First Search Frontier
Depth First Search Algorithm
follow path until you get stuck
backtrack along breadcrumbs until reach unexplored neighbor
recursively explore
careful not to repeat a vertex
parent = {s: None}
DFS-visit (V, Adj, s):
start for v in Adj [s]:
if v not in parent:
v
parent [v] = s
finish
DFS-visit (V, Adj, v)
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 3: Depth-First Search Algorithm
Example
S1
forward
edge
back
edge
cross edge
S2
6
back edge
Figure 4: Depth-First Traversal
Edge Classification
tree edges (formed by parent)
nontree edges
back edge: to ancestor
forward edge: to descendant
cross edge (to another subtree)
Figure 5: Edge Classification
to compute this classification (back or not), mark nodes for duration they are on the
stack
only tree and back edges in undirected graph
Analysis
DFS-visit gets called withX
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)
3
Cycle Detection
Graph G has a cycle DFS has a back edge
Proof
(<=)
tree edges
is a cycle
back edge: to tree ancestor
(=>)
consider first visit to cycle:
v3
v2
vk
v1
v0
FIRST!
before visit to vi finishes,
will visit vi+1 (& finish):
will consider edge (vi , vi+1 )
= visit vi+1 now or already did
= before visit to v0 finishes,
will visit vk (& didnt before)
= before visit to vk (or v0 ) finishes,
will see (vk , v0 ) as back edge
Job scheduling
Given Directed Acylic Graph (DAG), where vertices represent tasks & edges represent
dependencies, order tasks without violating dependencies
8
G
4
A
E
6
Figure 6: Dependence Graph: DFS Finishing Times
Source:
Source = vertex with no incoming edges
= schedulable at beginning (A,G,I)
Attempt:
BFS from each source:
from A finds A, BH, C, F
from D finds D, BE, CF slow . . . and wrong!
from G finds G, H
from I finds I
Topological Sort
Reverse of DFS finishing times (time at which DFS-Visit(v) finishes)
DFS-Visit(v)
...
order.append(v)
order.reverse()
Correctness
For any edge (u, v) u ordered before v, i.e., v finished before u
if u visited before v:
before visit to u finishes, will visit v (via (u, v) or otherwise)
= v finishes before u
if v visited before u:
graph is acyclic
= u cannot be reached from v
= visit to v finishes before visiting u
