dfs implementation and extensions we begin by providing python implementation of the basic depth-first search algorithmoriginally described with pseudo-code in code fragment our dfs function is presented in code fragment def dfs(gudiscovered) """perform dfs of the undiscovered portion of graph starting at vertex discovered is dictionary mapping each vertex to the edge that was used to discover it during the dfs ( should be "discoveredprior to the call newly discovered vertices will be added to the dictionary as result ""for every outgoing edge from for in incident edges( ) opposite( if not in discoveredv is an unvisited vertex discovered[ve is the tree edge that discovered dfs(gvdiscoveredrecursively explore from code fragment recursive implementation of depth-first search on graphstarting at designated vertex in order to track which vertices have been visitedand to build representation of the resulting dfs treeour implementation introduces third parameternamed discovered this parameter should be python dictionary that maps vertex of the graph to the tree edge that was used to discover that vertex as technicalitywe assume that the source vertex occurs as key of the dictionarywith none as its value thusa caller might start the traversal as followsresult { nonedfs(guresulta new dictionarywith trivially discovered the dictionary serves two purposes internallythe dictionary provides mechanism for recognizing visited verticesas they will appear as keys in the dictionary externallythe dfs function augments this dictionary as it proceedsand thus the values within the dictionary are the dfs tree edges at the conclusion of the process because the dictionary is hash-basedthe test"if not in discovered,and the record-keeping step"discovered[ve,run in ( expected timerather than worst-case time in practicethis is compromise we are willing to acceptbut it does violate the formal analysis of the algorithmas given on page if we could assume that vertices could be numbered from to then those numbers could be used as indices into an array-based lookup table rather than hash-based map alternativelywe could store each vertex' discovery status and associated tree edge directly as part of the vertex instance