# depthFirstSearch -- runs a depth first search on the digraph or digraph and returns the discovery time and finishing time for each vertex in the digraph

## Synopsis

• Usage:
dfs = depthFirstSearch D
dfs = depthFirstSearch G
• Inputs:
• D, an instance of the type Digraph
• G, an instance of the type Graph
• Outputs:
• dfs, , A hash table with keys discoveryTime and finishingTime, whose values are hash tables containing for each vertex the discovery time and finishing time, respectively.

## Description

A depth first search begins at the first vertex of a graph as a root and searches as far as possible along one branch from that root before backtracking to the next branch to the right. Discovery time denotes the order in which the vertex was searched first; finishing time denotes the time in which the vertex's descendents were all finished.

 i1 : D = digraph ({{0,1},{1,3},{1,4},{4,7},{4,8},{0,2},{2,5},{2,6}},EntryMode=>"edges") o1 = Digraph{0 => {1, 2}} 1 => {3, 4} 2 => {5, 6} 3 => {} 4 => {7, 8} 5 => {} 6 => {} 7 => {} 8 => {} o1 : Digraph i2 : dfs = depthFirstSearch D o2 = HashTable{discoveryTime => HashTable{0 => 1 }} 1 => 2 2 => 12 3 => 9 4 => 3 5 => 13 6 => 15 7 => 6 8 => 4 finishingTime => HashTable{0 => 18} 1 => 11 2 => 17 3 => 10 4 => 8 5 => 14 6 => 16 7 => 7 8 => 5 o2 : HashTable i3 : G = cycleGraph 6 o3 = Graph{0 => {1, 5}} 1 => {0, 2} 2 => {1, 3} 3 => {2, 4} 4 => {3, 5} 5 => {0, 4} o3 : Graph i4 : dfs = depthFirstSearch G o4 = HashTable{discoveryTime => HashTable{0 => 1 }} 1 => 10 2 => 5 3 => 4 4 => 3 5 => 2 finishingTime => HashTable{0 => 12} 1 => 11 2 => 6 3 => 7 4 => 8 5 => 9 o4 : HashTable