CS 310: Algorithms

Directed Graphs and Depth First Search

Instructor: Basit Shafiq
basit@lums.edu.pk
Office: 9-G12A
This topic is covered from:
• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Third Edition, July 2009. MIT Press (Chapter 22, Section 22.3), and
• Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2005.
• The slide contents are also modified from lecture slides by Kevin Wayne
(https://www.cs.princeton.edu/~wayne/kleinberg-tardos/)
Directed graphs

G = (V, E)
・ (u, v) u v

・
・
Road network
 Breadth First Search (BFS)

• BFS traverses the vertices of a graph from a given source node 𝑠 in

the order of the distances from the source
• Discovers all vertices at distance 𝑘 from 𝑠 before discovering any vertices at
distance 𝑘 + 1
• Outputs a BFS tree with root 𝑠

s L1 L2 Ln–1

4
 Depth First Search (DFS)

• DFS follows the strategy of going deep first and then wide
• DFS starts at the source node 𝑠 and explores as far as possible along each
branch before backtracking

Image source: https://vivadifferences.com/difference-between-dfs-and-bfs-in-artificial-intelligence/

5
 Depth First Search (DFS)

• Given a directed Graph, 𝐺 = (𝑉, 𝐸), DFS traverses all vertices of 𝐺

• Each vertex 𝑣 is labelled with a discovery time 𝑑. 𝑣 and finish time 𝑓. 𝑣
• 𝑑. 𝑣 denotes the time when vertex 𝑣 is first processed
• 𝑓. 𝑣 denotes the time when all of the descendants of 𝑣 are finished, i.e., when all the
paths originating from 𝑣 are processed.
• DFS colors the vertices during the search to indicate their state
• Initially all vertices are colored white
• White vertices are not discovered yet
• When a vertex is discovered it is colored gray
• Gray vertices are discovered, however all paths originating from a gray vertex are not
explored yet
• When a vertex is finished it is colored black
• All paths from a black vertex are explored

6
 DFS Algorithm
𝐺 = (𝑉, 𝐸)
DFS(𝑮) DFS-VISIT(𝑮, 𝒖)
1 for each vertex 𝑢 ∈ 𝑉 1 𝑡𝑖𝑚𝑒 = 𝑡𝑖𝑚𝑒 + 1 //white vertex 𝑢 has just been discovered
2 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑊𝐻𝐼𝑇𝐸 2 𝑢. 𝑑 = 𝑡𝑖𝑚𝑒
3 𝑢. 𝜋 = 𝑁𝐼𝐿 3 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝐺𝑅𝐴𝑌
4 𝑡𝑖𝑚𝑒 = 0 4 for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] // explore edge (𝑢, 𝑣)
5 for each vertex 𝑢 ∈ 𝑉 5 if 𝑣. 𝑐𝑜𝑙𝑜𝑟 == 𝑊𝐻𝐼𝑇𝐸
6 if 𝑢. 𝑐𝑜𝑙𝑜𝑟 == 𝑊𝐻𝐼𝑇𝐸 6 𝑣. 𝜋 = 𝑢
7 DFS-VISIT(𝐺, 𝑢) 7 DFS-VISIT(𝐺, 𝑣)
8 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝐵𝐿𝐴𝐶𝐾 //blacken 𝑢; it is finished
9 𝑡𝑖𝑚𝑒 = 𝑡𝑖𝑚𝑒 + 1
10 𝑢. 𝑓 = 𝑡𝑖𝑚𝑒

7
 DFS - Example
u v w u v w u v w
1/ 1/ 2/

x y z x y z x y z

(a) (b) (c)

u v w u v w u v w
1/ 2/ 1/ 2/ 1/ 2/
B

3/ 4/ 3/ 4/ 3/
x y z x y z x y z

(d) (e) (f)

8
 DFS – Example, Contd.
u v w u v w u v w
1/ 2/ 1/ 2/ 1/ 2/7
B B B

4/5 3/ 4/5 3/6 4/5 3/6

x y z x y z x y z
(g) (h) (i)

u v w u v w u v w
1/ 2/7 1/8 2/7 1/8 2/7 9/
F B F B F B

4/5 3/6 4/5 3/6 4/5 3/6

x y z x y z x y z
(j) (k) (l)

9
 DFS – Example, Contd.

u v w u v w
1/8 2/7 9/ 1/8 2/7 9/
F B C F B C

4/5 3/6 4/5 3/6 10/

x y z x y z
(m) (n)

u v w u v w
1/8 2/7 9/ 1/8 2/7 9/12
F B C F B C

4/5 3/6 10/11 4/5 3/6 10/11

x y z x y z
(o) (p)
10
 Depth First Search (DFS)

• Given a directed Graph, 𝐺 = (𝑉, 𝐸), DFS traverses all vertices of 𝐺

• Each vertex 𝑣 is labelled with a discovery time 𝑑. 𝑣 and finish time 𝑓. 𝑣
• 𝑑. 𝑣 denotes the time when vertex 𝑣 is first processed
• 𝑓. 𝑣 denotes the time when all of the descendants of 𝑣 are finished, i.e., when all the
paths originating from 𝑣 are processed.
• DFS creates a forest 𝐺𝜋 = (𝑉, 𝐸𝜋 ), a collection of rooted trees, where
• 𝐸𝜋 = { 𝑣. 𝜋, 𝑣 : 𝑣 ∈ 𝑉 and 𝑣. 𝜋 ≠ NIL}
• All the edges in 𝐸𝜋 are tree edges

11
 Depth-first forest

u v w u v w
1/8 2/7 9/12 1/8 2/7 9/12
F B C

4/5 3/6 10/11 4/5 3/6 10/11

x y z x y z

𝐺𝜋 = 𝑉, 𝐸𝜋

𝑉 = 𝑢, 𝑣, 𝑤, 𝑥, 𝑦, 𝑧

𝐸𝜋 = { 𝑢, 𝑣 , 𝑣, 𝑦 , 𝑦, 𝑥 , 𝑤, 𝑧 }

12
Depth-first forest

13
 DFS – Classification of Edges

• Tree edges are edges in the depth-first

forest 𝐺𝜋 . Edge (𝑢, 𝑣) is a tree edge if 𝑣
was discovered by exploring edge (𝑢, 𝑣)
• Back edges are those edges (𝑢, 𝑣)
connecting a vertex 𝑢 to an ancestor
vertex 𝑣 in a depth-first tree. Self-loop
(edge (𝑢, 𝑢)), is also considered as Back
edge
• Forward edges are those nontree edges
(𝑢, 𝑣) connecting a vertex 𝑢 to an
descendent vertex 𝑣 in a depth-first tree.
• Cross edges are all other edges. These
can connect two vertices:
• In the same depth-first tree as long as one
vertex is not the descendent of the other, or
• in different depth-first trees

14
 Running time of DFS
DFS(𝑮) DFS-VISIT(𝑮, 𝒖)
1 for each vertex 𝑢 ∈ 𝑉 1 𝑡𝑖𝑚𝑒 = 𝑡𝑖𝑚𝑒 + 1
• Loops on lines 1-3 and lines 5-7 take time Θ 𝑉 ,
2 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑊𝐻𝐼𝑇𝐸 2 𝑢. 𝑑 = 𝑡𝑖𝑚𝑒 exclusive of the time to execute the calls to
3 𝑢. 𝜋 = 𝑁𝐼𝐿 3 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝐺𝑅𝐴𝑌 DFS-VISIT
4 𝑡𝑖𝑚𝑒 = 0 4 for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] • DFS-VISIT is called exactly once for each 𝑣 ∈ 𝑉
5 for each vertex 𝑢 ∈ 𝑉 5 if 𝑣. 𝑐𝑜𝑙𝑜𝑟 == 𝑊𝐻𝐼𝑇𝐸 • During an execution of DFS-VISIT(𝐺, 𝑣), the
6 if 𝑢. 𝑐𝑜𝑙𝑜𝑟 == 𝑊𝐻𝐼𝑇𝐸 6 𝑣. 𝜋 = 𝑢 loop on lines 4-7 executes |𝐴𝑑𝑗 𝑣 | times.
7 DFS-VISIT(𝐺, 𝑢) 7 DFS-VISIT(𝐺, 𝑣) • Since
8 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝐵𝐿𝐴𝐶𝐾 σ𝑣∈𝑉 |𝐴𝑑𝑗 𝑣 | = Θ 𝐸 ,

9 𝑡𝑖𝑚𝑒 = 𝑡𝑖𝑚𝑒 + 1 the total cost of executing lines 4-7 of DFS-VISIT is

10 𝑢. 𝑓 = 𝑡𝑖𝑚𝑒
Θ 𝐸

• Therefore, the running time of DFS is

Θ |𝑉| + |𝐸|

15
Strong connectivity

u v u v v
u

s G s s


 u v u↝s s↝v
v u v↝s s↝u ▪
Strong connectivity: algorithm

G O(m + n)

・ s
・ s G
・ s G reverse
・
・ ▪

strongly connected not strongly connected

Strong components

O(m + n)
Algorithm for finding strong components in a directed graph

STRONG-COMPONENTS(𝑮)
1 Call DFS(G) to compute finishing times 𝑢. 𝑓 for each vertex 𝑢
2 Compute 𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒
3 Call DFS(𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 ), but in the main loop of DFS, consider the
vertices in order of decreasing 𝑢. 𝑓 as computed in line 1
4 Output the vertices of each tree in the depth-first forest formed in
line 3 as a separate strong component

19
 Strong components - example
a b c d

e f g h

1 Call DFS(G) to compute finishing times 𝑢. 𝑓 for each vertex 𝑢

a b c d

13/14 11/16 1/10 8/9

12/15 3/4 2/7 5/6

e f g h
20
 Strong components – example, contd
a b c d

13/14 11/16 1/10 8/9

𝐺
12/15 3/4 2/7 5/6

e f g h

2 Compute 𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒
a b c d

𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒

e f g h
21
 Strong components – example, contd
a b c d

13/14 11/16 1/10 8/9

𝐺
12/15 3/4 2/7 5/6

e f g h
3 Call DFS(𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 ), but in the main loop of DFS, consider the
vertices in order of decreasing 𝑢. 𝑓 as computed in line 1
a b c d

𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒

e f g h
22
 Strong components – example, contd
a b c d

13/14 11/16 1/10 8/9

𝐺
12/15 3/4 2/7 5/6

e f g h
3 Call DFS(𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 ), but in the main loop of DFS, consider the
vertices in order of decreasing 𝑢. 𝑓 as computed in line 1
a b c d
2/5 1/6 7/10 8/9

𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒
3/4 12/13 11/14 15/16

e f g h 23
 Strong components – example, contd
4 Output the vertices of each tree in the depth-first forest formed in
line 3 as a separate strong component
a b c d
2/5 1/6 7/10 8/9

𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒
3/4 12/13 11/14 15/16

e f g h

24
 Strong components – example, contd
a b c d

13/14 11/16 1/10 8/9

𝐺
12/15 3/4 2/7 5/6

e f g h

a b c d
2/5 1/6 7/10 8/9

𝐺 𝑟𝑒𝑣𝑒𝑟𝑠𝑒
3/4 12/13 11/14 15/16

e f g h
25