reconstructing path from to we can use the basic dfs function as tool to identify the (directedpath leading from vertex to vif is reachable from this path can easily be reconstructed from the information that was recorded in the discovery dictionary during the traversal code fragment provides an implementation of secondary function that produces an ordered list of vertices on the path from to to reconstruct the pathwe begin at the end of the pathexamining the discovery dictionary to determine what edge was used to reach vertex vand then what the other endpoint of that edge is we add that vertex to listand then repeat the process to determine what edge was used to discover it once we have traced the path all the way back to the starting vertex uwe can reverse the list so that it is properly oriented from to vand return it to the caller this process takes time proportional to the length of the pathand therefore it runs in (ntime (in addition to the time originally spent calling dfs def construct path(uvdiscovered) path empty path by default if in discovered we build list from to and then reverse it at the end path append( walk while walk is not discovered[walkfind edge leading to walk parent opposite(walk path append(parent walk parent path reversereorient path from to return path code fragment function to reconstruct directed path from to vgiven the trace of discovery from dfs started at the function returns an ordered list of vertices on the path testing for connectivity we can use the basic dfs function to determine whether graph is connected in the case of an undirected graphwe simply start depth-first search at an arbitrary vertex and then test whether len(discoveredequals at the conclusion if the graph is connectedthen by proposition all vertices will have been discoveredconverselyif the graph is not connectedthere must be at least one vertex that is not reachable from uand that will not be discovered