Depth-First Search

1
 Depth-First Search
• Graph G(V,E) directed or undirected
• Adjacency list representation
• Goal: Systematically explore every vertex and
every edge
• Idea: search deeper whenever possible
– Using a LIFO queue (Stack; FIFO queue used in BFS)

2
 Depth-First Search
• Maintains several fields for each vV
• Like BFS, colors the vertices to indicate their
states. Each vertex is
– Initially white,
– grayed when discovered,
– blackened when finished
• Like BFS, records discovery of a white v during
scanning Adj[u] by [v] u

3
 Depth-First Search
• Unlike BFS, predecessor graph G produced by
DFS forms spanning forest
• G(V,E) where
E{([v],v): vV and [v] NIL}
• G depth-first forest (DFF) is composed of
disjoint depth-first trees (DFTs)

4
 Depth-First Search
• DFS also timestamps each vertex with two timestamps
• d[v]: records when v is first discovered and grayed
• f[v]: records when v is finished and blackened
• Since there is only one discovery event and finishing
event for each vertex we have 1 d[v]  f[v] 2|V|
Time axis for the color of a vertex

1 2 d[v] f[v] 2|V|

5
 Depth-First Search
DFS(G) DFS-VISIT(G, u)
for each uV do color[u] gray
color[u] white d[u] time  time 1
[u]  NIL for each v Adj[u] do
time  0 if color[v]  white then
for each uV do [v]  u
DFS-VISIT(G, v)
if color[u]  white then
DFS-VISIT(G, u) color[u] black
f[u] time  time 1

6
 Depth-First Search
• Running time: (VE)
• Initialization loop in DFS : (V)
• Main loop in DFS: (V) exclusive of time to execute
calls to DFS-VISIT
• DFS-VISIT is called exactly once for each vV since
– DFS-VISIT is invoked only on white vertices and
– DFS-VISIT(G, u) immediately colors u as gray
• For loop of DFS-VISIT(G, u) is executed |Adj[u]| time
• Since  |Adj[u]|  E, total cost of executing loop of
DFS-VISIT is (E)

7
Depth-First Search: Example
x y z

s t

w v u

8
Depth-First Search: Example
x y z
1

s t

w v u

9
Depth-First Search: Example
x y z
1

s t
2

w v u

10
Depth-First Search: Example
x y z
1

s t
2

w v u

11
Depth-First Search: Example
x y z
1

s t
2

w v u

12
Depth-First Search: Example
x y z
1

s t
2

3 4

w v u

13
Depth-First Search: Example
x y z
1

s t
2

3 4 5

w v u

14
Depth-First Search: Example
x y z
1

s t
2

3 4 5

w v u

15
Depth-First Search: Example
x y z
1

s t
2

3 4 5 6

w v u

16
Depth-First Search: Example
x y z
1

s t
2 7

3 4 5 6

w v u

17
Depth-First Search: Example
x y z
1 8

s t
2 7

3 4 5 6

w v u

18
Depth-First Search: Example
x y z
1 8

s t
2 7

3 4 5 6

w v u

19
Depth-First Search: Example
x y z
1 8

s t
2 7 9

3 4 5 6

w v u

20
Depth-First Search: Example
x y z
1 8

s t
2 7 9

3 4 5 6

w v u

21
Depth-First Search: Example
x y z
1 8

s t
2 7 9 10

3 4 5 6

w v u

22
Depth-First Search: Example
x y z
1 8 11

s t
2 7 9 10

3 4 5 6

w v u

23
Depth-First Search: Example
x y z
1 12 8 11

s t
2 7 9 10

3 4 5 6

w v u

24
Depth-First Search: Example
x y z
1 12 8 11 13

s t
2 7 9 10

3 4 5 6

w v u

25
Depth-First Search: Example
x y z
1 12 8 11 13

s t
2 7 9 10

3 4 5 6

w v u

26
Depth-First Search: Example
x y z
1 12 8 11 13

s t
2 7 9 10

3 4 5 6

w v u

27
Depth-First Search: Example
x y z
1 12 8 11 13

s t
2 7 9 10

3 4 5 6 14

w v u

28
Depth-First Search: Example
x y z
1 12 8 11 13

s t
2 7 9 10

3 4 5 6 14

w v u

29
Depth-First Search: Example
x y z
1 12 8 11 13

s t
2 7 9 10

3 4 5 6 14 15

w v u

30
Depth-First Search: Example
x y z
1 12 8 11 13 16

s t
2 7 9 10

3 4 5 6 14 15

w v u

31
 Depth-First Search: Example
DFS(G) terminated Depth-first forest (DFF)

x y z x y z
1 12 8 11 13 16 1 12 8 11 13 16

s t s t
2 7 9 10 2 7 9 10

3 4 5 6 14 15 3 4 5 6 14 15

w v u w v u

32
 Slide Credits
• Ata Turk, Bilkent University

33