Implementing Depth First Search Section 3 3 DFS Implementation 1 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 8 5 1 6 Explored nodes shown in red Stack DFS Execution 7 1 3 2 4 5 8 2 3 6 Explored nodes shown in red Stack 2 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 1 5 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 3 2 4 5 8 5 3 4 3 6 Explored nodes in red Stack 3 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 2 3 6 4 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 3 2 4 5 3 6 4 3 4 3 8 6 Explored nodes in red Stack 4 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 5 2 8 7 6 4 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 4 2 8 7 6 4 3 4 3 3 2 5 8 6 Explored nodes in red Stack 5 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 8 7 6 4 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 4 7 3 7 6 4 3 4 3 3 2 5 8 6 Explored nodes in red Stack 6 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 8 3 3 7 6 4 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 4 3 3 7 6 4 3 4 3 3 2 5 8 6 Explored nodes in red Stack 7 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 3 7 6 4 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 3 2 4 5 7 6 4 3 4 3 8 6 Explored nodes in red Stack 8 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 6 4 3 4 3 8 5 6 Explored nodes in red Stack DFS Execution 7 1 3 2 4 5 5 4 3 4 3 8 6 Explored nodes in red Stack 9 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 8 5 4 3 4 3 6 Explored nodes in red Stack DFS Execution 7 1 3 2 4 5 5 2 3 4 3 8 6 Explored nodes in red Stack 10 PDF created with pdfFactory trial version www pdffactory com DFS Execution 7 1 3 2 4 5 8 6 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 www pdffactory com 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 p Adding and Deleting nodes to stack S Count node additions and deletions 12 PDF created with pdfFactory trial version www pdffactory com DFS Running Time p Main steps in the Algo n Adding and Deleting nodes to stack S Count node additions and deletions p Number of additions Number of deletions p 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 Count node additions and deletions p Number of additions Number of deletions p n p Enough to count number of node additions Number of times node u gets added du the degree of u 13 PDF created with pdfFactory trial version www pdffactory com DFS Running Time p Main steps in the Algo n Adding and Deleting nodes to stack S Count node additions and deletions p Number of additions Number of deletions p n p Enough to count number of node additions 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 www pdffactory com