Chapter 22
Graph Algorithms - DFS
PART-3
Outlines: Graphs Part-3
Depth-First Search:
DFS Algorithm
DFS Example
DFS Running Time
DFS Predecessor Subgraph
DFS Time Stamping
DFS Edge Classification
DFS and Graph Cycles
1
Depth-First Search
Depth-first search is another strategy for exploring a
graph
Explore “deeper” in the graph whenever possible
Edges are explored out of the most recently
discovered vertex v that still has unexplored
edges
When all of v’s edges have been explored,
backtrack to the vertex from which v was
discovered
Depth-First Search
Initialize
color all vertices white
Visit each and every white vertex using DFS-Visit
Each call to DFS-Visit(u) roots a new tree of the
depth-first forest at vertex u
A vertex is white if it is undiscovered
A vertex is gray if it has been discovered but not all
of its edges have been discovered
A vertex is black after all of its adjacent vertices
have been discovered (the adj. list was examined
completely)
2
Depth-First Search
Init all
vertices
Visit all
children
recursively
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
for each vertex u V[G] color[u] = GRAY;
{ time = time+1;
color[u] = WHITE;
d[u] = time;
p[u] = NIL;
} for each v Adj[u]
time = 0;
for each vertex u V[G] if (color[v] == WHITE)
{ p[v] = u;
if (color[u] == WHITE) DFS_Visit(v);
DFS_Visit(u);
} color[u] = BLACK;
} time = time+1;
f[u] = time;
}
3
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
for each vertex u V[G] color[u] = GRAY;
{ time = time+1;
color[u] = WHITE; d[u] = time;
p[u] = NIL; for each v Adj[u]
}
time = 0; if (color[v] == WHITE)
for each vertex u V[G] p[v] = u;
{ DFS_Visit(v);
if (color[u] == WHITE)
DFS_Visit(u); color[u] = BLACK;
} time = time+1;
} f[u] = time;
}
What does d[u] represent?
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
for each vertex u V[G] color[u] = GRAY;
{ time = time+1;
color[u] = WHITE;
d[u] = time;
p[u] = NIL
} for each v Adj[u]
time = 0;
for each vertex u V[G] if (color[v] == WHITE)
{ p[v] = u;
if (color[u] == WHITE) DFS_Visit(v);
DFS_Visit(u);
} color[u] = BLACK;
} time = time+1;
f[u] = time;
}
What does f[u] represent?
4
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
1 for each vertex u V[G] 1 color[u] = GRAY;
{ 2 time = time+1;
2 color[u] = WHITE; 3 d[u] = time;
3 p[u] = NIL 4 for each v Adj[u]
}
4 time = 0; 5 if (color[v] == WHITE)
5 for each vertex u V[G] 6 p[v] = u;
{ 7 DFS_Visit(v);
6 if (color[u] == WHITE)
7 DFS_Visit(u); 8 color[u] = BLACK;
} 9 time = time+1;
} 10 f[u] = time;
}
Will all vertices eventually be colored black?
Depth-First Search: DFS Procedure
Lines 1-3 paint all vertices white and initialize their
p fields to NIL.
Line 4 resets the global time counter.
Lines 5-7 check each vertex in V in turn and, when a
white vertex is found, visit it using DFS_Visit.
Every time DFS-Visit(u) is called in line 7,
vertex u becomes the root of a new tree in the
depth-first forest.
When DFS returns, every vertex u has been assigned
a discovery time d[u] and a finishing time f[u].
10
5
Depth-First Search: DFS-Visit Procedure
In each call DFS-Visit(u), vertex u is initially white.
Line 1 paints u gray.
Line 2 increments the global variable time.
Line 3 records the new value of time as the discovery
time d[u].
Lines 4-7 examine each vertex v adjacent to u and
recursively visit v if it is white.
As each vertex v Adj[u] is considered in line 4,
we say that edge (u, v) is explored by the depth-
first search.
Finally, after every edge leaving u has been
explored, lines 8-10 paint u black and record the
finishing time in f[u].
11
DFS Example
source
vertex
12
6
DFS Example
source
vertex
d f
1 | | |
| |
| | |
13
DFS Example
source
vertex
d f
1 | | |
2 | |
| | |
14
7
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | | |
15
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 | |
16
8
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 5 | |
17
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 5 | 6 |
18
9
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
19
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |
3 | 4 5 | 6 |
What is the structure of the gray vertices?
What do they represent?
20
10
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |10
3 | 4 5 | 6 |
21
DFS Example
source
vertex
d f
1 | 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
22
11
DFS Example
source
vertex
d f
1 |12 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
23
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 |
24
12
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|
25
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|15
26
13
DFS Example
source
vertex
d f
1 |12 8 |11 13|16
2 | 7 9 |10
3 | 4 5 | 6 14|15
27
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
for each vertex u V[G] color[u] = GRAY;
{ time = time+1;
color[u] = WHITE;
d[u] = time;
p[u] = NIL
} for each v Adj[u]
time = 0;
for each vertex u V[G] if (color[v] == WHITE)
{ p[v] = u;
if (color[u] == WHITE) DFS_Visit(v);
DFS_Visit(u);
} color[u] = BLACK;
} time = time+1;
f[u] = time;
}
What will be the running time?
28
14
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
for each vertex u V[G] color[u] = GRAY;
{ time = time+1;
color[u] = WHITE; d[u] = time;
p[u] = NIL for each v Adj[u]
}
time = 0; if (color[v] == WHITE)
for each vertex u V[G] p[v] = u;
{
(V) if (color[u] == WHITE)
DFS_Visit(v);
DFS_Visit(u);
} color[u] = BLACK;
} time = time+1;
f[u] = time;
}
How many times will DFS_Visit() actually be called? (V)
How many times will if statement be executed in all O(V) DFS_Visit calls?
(E)
29
Depth-First Search: Algorithm
DFS(G) DFS_Visit(u)
{ {
for each vertex u V[G] color[u] = GRAY;
{ time = time+1;
color[u] = WHITE;
d[u] = time;
p[u] = NIL
} for each v Adj[u]
time = 0;
for each vertex u V[G] if (color[v] == WHITE)
{ p[v] = u;
if (color[u] == WHITE) DFS_Visit(v);
DFS_Visit(u);
} color[u] = BLACK;
} time = time+1;
f[u] = time;
}
So, running time of DFS = (V+E)
30
15
DFS: Running Time
Running time
the loops in DFS take time (V) each, excluding the
time to execute DFS-Visit
DFS-Visit is called once for every vertex
its only invoked on white vertices, and
paints the vertex gray immediately
for each DFS-Visit(v) a loop iterates over all Adj[v]
the total cost for DFS-Visit is (E)
Adj[v] ( E )
vV
the running time of DFS is (V+E)
31
Predecessor Subgraph
Define slightly different from BFS
Defined the predecessor subgraph of G as Gp= (V, Ep),
where
Ep = {(p[v], v) E : v V and p[v] NIL}
The PD subgraph of a depth-first search forms a depth-
first forest composed of several depth-first trees
The edges in Gp are called tree edges
32
16
DFS Timestamping
The DFS algorithm maintains a monotonically increasing
global clock
discovery time d[u] and finishing time f[u]
For every vertex u, the inequality d[u] f[u] must hold
33
DFS Timestamping
Vertex u is
white before time d[u]
gray between time d[u] and time f[u], and
black thereafter
Notice the structure througout the algorithm.
gray vertices form a linear chain
correponds to a stack of vertices that have not
been exhaustively explored (DFS-Visit started
but not yet finished)
What is the size of the stack in DFS?
34
17
DFS Edge Classification
Tree edge (gray to white)
encounter new vertices (white)
included in depth-first forest Gp
Back edge (gray to gray)
from descendant to ancestor
non-tree edges in depth-first tree
35
DFS Edge Classification
Forward edge (gray to black): if d[u] d[v]
from ancestor to descendant
non-tree edges in depth-first tree
Cross edge (gray to black): if d[u] d[v]
are all other edges
between trees or subtrees
36
18
DFS Edge Classification
Tree and back edges are important
Most algorithms do not distinguish between
forward and cross edges
37
DFS Example
source
vertex
d f
1 |12 8 |11 13|16
2 | 7 9 |10
3 | 4 5 | 6 14|15
Tree edges Back edges Forward edges Cross edges
38
19
DFS: Kinds Of Edges
Theorem 22.10:
If G is undirected, a DFS produces only tree and
back edges
source
Proof by contradiction: u
Assume there’s a forward edge
But F? edge must actually be a F?
back edge (why?)
v
Since edge (w, u) is from
descendant to ancestor
(gray to gray)
w
39
DFS: Kinds Of Edges
Theorem 22.10:
If G is undirected, a DFS produces only tree and back edges
Proof by contradiction:
Assume there’s a cross edge
source
But C? edge cannot be cross:
must be explored from one of the
vertices it connects, becoming a tree
vertex, before other vertex is explored
So in fact the picture is wrong…both
blue and red edges cannot in fact be
tree edges.
One should be tree edge and
the other should be back edge (cycle graph) C?
40
20
DFS and Graph Cycles
Theorem:
An undirected graph is acyclic (no cycles) iff a
DFS yields no back edges
If acyclic, no back edges (because a back edge
implies a cycle
If no back edges, acyclic
No back edges implies only tree edges (Why?)
Only tree edges implies we have a tree or a forest
Which by definition is acyclic
Thus, can run DFS to find whether a graph has a
cycle. (How)
41
DFS Example
u v w u v w u v w
1/ 1/ 2/ 1/ 2/
3/
x y z x y z x y z
u v w u v w u v w
1/ 2/ 1/ 2/ 1/ 2/
B B
4/ 3/ 4/ 3/ 4/5 3/
x y z x y z x y z
42
21
DFS Example
u v w u v w u v w
1/ 2/ 1/ 2/7 1/ 2/7
B B F B
4/5 3/6 4/5 3/6 4/5 3/6
x y z x y z x y z
u v w u v w u v w
1/8 2/7 1/8 2/7 9/ 1/8 2/7 9/
B B B C
F F F
4/5 3/6 4/5 3/6 4/5 3/6
x y z x y z x y z
43
DFS Example
u v w u v w u v w
1/8 2/7 9/ 1/8 2/7 9/ 1/8 2/7 9/
B C B C B C
F F F
4/5 3/6 10/ 4/5 3/6 10/ B 4/5 3/6 10/11 B
x y z x y z x y z
u v w
If you have a back edge in a
1/8 2/7 9/12
F B C directed graph, then you may have
4/5 3/6 10/11 a cycle or must have a cycle?
B
x y z
44
22
