chap graphs ( (bfigure (aa graph (bthe depth-first search tree for the graph when starting at vertex the edges that were followed to any new (unvisitedvertex during the traversal and leaves out the edges that lead to already visited vertices dfs can be applied to directed or undirected graphs here is an implementation for the dfs algorithmstatic void dfs(graph gint /depth first search previsit(gv)/take appropriate action setmark(vvisited)for (int first( ) ( next(vw)if ( getmark( =unvisiteddfs(gw)postvisit(gv)/take appropriate action this implementation contains calls to functions previsit and postvisit these functions specify what activity should take place during the search just as preorder tree traversal requires action before the subtrees are visitedsome graph traversals require that vertex be processed before ones further along in the dfs alternativelysome applications require activity after the remaining vertices are processedhence the call to function postvisit this would be natural opportunity to make use of the visitor design pattern described in section figure shows graph and its corresponding depth-first search tree figure illustrates the dfs process for the graph of figure (adfs processes each edge once in directed graph in an undirected graphdfs processes each edge from both directions each vertex must be visitedbut only onceso the total cost is th(| | |