graph algorithms void graph::dfsvertex visited truefor each vertex adjacent to if! visited dfsw )figure template for depth-first search (pseudocodeapply depth-first traversal thereand continue this process until there are no unmarked nodes because this strategy guarantees that each edge is encountered only oncethe total time to perform the traversal is (| | |)as long as adjacency lists are used undirected graphs an undirected graph is connected if and only if depth-first search starting from any node visits every node because this test is so easy to applywe will assume that the graphs we deal with are connected if they are notthen we can find all the connected components and apply our algorithm on each of these in turn as an example of depth-first searchsuppose in the graph of figure we start at vertex then we mark as visited and call dfs(brecursively dfs(bmarks as visited and calls dfs(crecursively dfs(cmarks as visited and calls dfs(drecursively dfs(dsees both and bbut both of these are markedso no recursive calls are made dfs(dalso sees that is adjacent but markedso no recursive call is made thereand dfs(dreturns back to dfs(cdfs(csees adjacentignores itfinds previously unseen vertex adjacentand thus calls dfs(edfs(emarks eignores and cand returns to dfs(cdfs(creturns to dfs(bdfs(bignores both and and returns dfs(aignores both and and returns (we have actually touched every edge twiceonce as (vwand again as (wv)but this is really once per adjacency list entry we graphically illustrate these steps with depth-first spanning tree the root of the tree is athe first vertex visited each edge (vwin the graph is present in the tree ifwhen we process (vw)we find that is unmarkedor ifwhen we process (wv)we find that is unmarkedwe indicate this with tree edge ifwhen we process (vw)we find that is already markedand when processing (wv)we find that is already markedwe draw dashed linewhich we will call back edgeto indicate that this "edgeis not really part of the tree the depth-first search of the graph in figure is shown in figure the tree will simulate the traversal we performed preorder numbering of the treeusing only tree edgestells us the order in which the vertices were marked if the graph is not connectedthen processing all nodes (and edgesrequires several calls to dfsand each generates tree this entire collection is depth-first spanning forest an efficient way of implementing this is to begin the depth-first search at if we need to restart the depth-first searchwe examine the sequence vk vk+ for an unmarked vertexwhere vk- is the vertex where the last depth-first search was started this guarantees that throughout the algorithmonly (| |is spent looking for vertices where new depth-first search trees can be started