Implementing Depth-First
Search
Section 3.3
DFS Implementation
1
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
4 5 8
6 1
Explored nodes (shown in red) Stack
DFS Execution
1 7
2 3
4 5 8
2
6 3
Explored nodes (shown in red) Stack
2
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
1
4 5 8
5
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
2 3
4 5 8
5
3
4
6 3
Explored nodes (in red) Stack
3
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
2
3
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
2 3
3
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
4
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
5
2
2 3
8
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
2
2 3
8
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
5
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
8
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
7
2 3
3
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
6
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
8
3
2 3
3
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
3
2 3
3
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
7
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
3
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
2 3
7
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
8
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
6
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
2 3
5
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
9
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
4 5 8
4
3
4
6 3
Explored nodes (in red) Stack
DFS Execution
1 7
2 3
5
4 5 8
2
3
4
6 3
Explored nodes (in red) Stack
10
PDF created with pdfFactory trial version [Link]
DFS Execution
1 7
2 3
4 5 8
Explored nodes (in red) Stack
DFS Running Time
p Running Time of DFS = O(m + n)
n Same as BFS
11
PDF created with pdfFactory trial version [Link]
DFS Running Time
p Main steps in the Algo.
n Adding and Deleting nodes to stack S
DFS Running Time
p Main steps in the Algo.
n Adding and Deleting nodes to stack S
p Count node additions and deletions
12
PDF created with pdfFactory trial version [Link]
DFS Running Time
p Main steps in the Algo.
n Adding and Deleting nodes to stack S
p Count node additions and deletions
p Number of additions=Number of deletions
n Enough to count number of node additions
DFS Running Time
p Main steps in the Algo.
n Adding and Deleting nodes to stack S
p Count node additions and deletions
p Number of additions=Number of deletions
n Enough to count number of node additions
p Number of times node u gets added
= du (the degree of u)
13
PDF created with pdfFactory trial version [Link]
DFS Running Time
p Main steps in the Algo.
n Adding and Deleting nodes to stack S
p Count node additions and deletions
p Number of additions=Number of deletions
n Enough to count number of node additions
p Number of times node u gets added
= du (the degree of u)
p Total Running time = O(Σu du) = O(m+n)
14
PDF created with pdfFactory trial version [Link]