Depth-First Search
Overview
› Depth-first and breadth-first (next section) searches are two classic and diametrically opposed ways to systematically process the vertices of a graph
Depth-first strategy
› Let V be an initially empty set of visited vertices
› Process and place the starting vertex s in V
› The next (unvisited) vertex to process and place in V is the furthest (deepest) vertex from s that is adjacent to a vertex along the current path
› Underlying data structure: Stack (recursion)
Alternate descriptions
› “Explore the graph one path at time.”
› “Explore the graph along a path from the starting vertex for as long as possible before backing up to explore another path.”
Basic algorithm
Depthfirstsearch (vertex v) mark v as visited
process v
for each unvisited adjacent vertex w to v do
Depthfirstsearch(w)
Vertex visited and on the current path
Vertex visited but not on the current path Vertex not visited
E
Current path
CDF
ABLHG
KJ
I
D
E
CDF
ABLHG
KJ
I
DC
E
CDF
ABLHG
KJ
I
DCB
E
CDF
ABLHG
KJ
I
DCBA
E
CDF
ABLHG
KJ
I
DCBAK
E
CDF
ABLHG
KJ
I
DCBAKJ
E
CDF
ABLHG
KJ
I
DCBAKJL
E
CDF
ABLHG
KJ
I
DCBAKJL
E
CDF
ABLHG
KJ
I
DCBAKJL
E
CDF
ABLHG
KJ
I
DCBAKJL
E
CDF
ABLHG
KJ
I
DCBAKJL
E
CDF
ABLHG
KJ
I
DCBAKJLE
E
CDF
ABLHG
KJ
I
DCBAKJLEH
E
CDF
ABLHG
KJ
I
DCBAKJLEHF
E
CDF
ABLHG
KJ
I
DCBAKJLEHFG
E
CDF
ABLHG
KJ
I
DCBAKJLEHFG
E
CDF
ABLHG
KJ
I
DCBAKJLEHFG
E
CDF
ABLHG
KJ
I
DCBAKJLEHFGI
E
CDF
ABLHG
KJ
I
DCBAKJLEHFGI
E
CDF
ABLHG
KJ
I
DCBAKJLEHFGI
E
CDF
ABLHG
KJ
I
Vertices are processed in this order DCBAKJLEHFGI
E
CDF
ABLHG
KJ
I
Breadth-First Search
Breadth-first strategy
› Let V be an initially empty set of visited vertices
› Let Q be an initially empty queue of vertices
› Place the starting vertex s in both V and Q
› The next vertex v to process is retrieved and removed from the front of Q. Once v is processed, each of its unvisited adjacent vertices is placed in V and Q
› Underlying data structure: Queue
Alternate descriptions
› “Explore vertices of a graph level-by-level from the starting vertex.”
Basic algorithm
Breadthfirstsearch (vertex v) mark v as visited
Q.Enqueue(v)
while !Q.Empty() do
v = Q.Dequeue();
process v
for each unvisited adjacent vertex w to v do
mark w as visited Q.Enqueue(w)
E
Q
Visited
Visited + Processed
CDF
ABLHG
KJ
I
E
Q
D
CDF
ABLHG
KJ
I
E
Q
C
E
H
D
CDF
ABLHG
KJ
I
E
Q
E
H
B
L
DC
CDF
ABLHG
KJ
I
E
Q
H
B
L
DCE
CDF
ABLHG
KJ
I
E
Q
B
L
F
G
I
DCEH
CDF
ABLHG
KJ
I
E
Q
L
F
G
I
A
K
DCEHB
CDF
ABLHG
KJ
I
E
Q
F
G
I
A
K
J
DCEHBL
CDF
ABLHG
KJ
I
E
Q
G
I
A
K
J
DCEHBLF
CDF
ABLHG
KJ
I
E
Q
I
A
K
J
DCEHBLFG
CDF
ABLHG
KJ
I
E
Q
A
K
J
DCEHBLFGI
CDF
ABLHG
KJ
I
E
Q
K
J
DCEHBLFGIA
CDF
ABLHG
KJ
I
E
Q
J
DCEHBLFGIAK
CDF
ABLHG
KJ
I
E
Q
DCEHBLFGIAKJ
Vertices are processed in this order
CDF
ABLHG
KJ
I
Note that all vertices at distance of i from the starting vertex are processed before all vertices at distance i+1
Vertex Distance
Implication
Once a vertex is processed, the shortest path to that vertex has been found!
D
C
E
H
B
L
F
G
I
A
K
J
0
1
2
3
Consider the following binary tree T
W
Q TVCS
GKDA M
B
Exercise
› Perform a depth-first and breadth-first search on T starting at vertex W
› Output in each case, the vertices as they are processed
› If the search begins at vertex Q, how does the depth-first or breadth-first search proceed to explore the entire tree T?