figure graph remaining after the path the total work performed on the vertex search phase is (| |during the entire life of the algorithm with the appropriate data structuresthe running time of the algorithm is (| | | very similar problem is to find simple cyclein an undirected graphthat visits every vertex this is known as the hamiltonian cycle problem although it seems almost identical to the euler circuit problemno efficient algorithm for it is known we shall see this problem again in section directed graphs using the same strategy as with undirected graphsdirected graphs can be traversed in linear timeusing depth-first search if the graph is not strongly connecteda depth-first search starting at some node might not visit all nodes in this casewe repeatedly perform depth-first searchesstarting at some unmarked nodeuntil all vertices have been visited as an exampleconsider the directed graph in figure we arbitrarily start the depth-first search at vertex this visits vertices bcadeand we then restart at some unvisited vertex arbitrarilywe start at hwhich visits and finallywe start at gwhich is the last vertex that needs to be visited the corresponding depth-first search tree is shown in figure the dashed arrows in the depth-first spanning forest are edges (vwfor which was already marked at the time of consideration in undirected graphsthese are always back edgesbutas we can seethere are three types of edges that do not lead to new vertices firstthere are back edgessuch as (aband (ihthere are also forward edgessuch as (cdand (ce)that lead from tree node to descendant finallythere are cross edgessuch as (fcand (gf)which connect two tree nodes that are not directly related depthfirst search forests are generally drawn with children and new trees added to the forest from left to right in depth-first search of directed graph drawn in this mannercross edges always go from right to left some algorithms that use depth-first search need to distinguish between the three types of nontree edges this is easy to check as the depth-first search is being performedand it is left as an exercise