running time of depth-first search in terms of its running timedepth-first search is an efficient method for traversing graph note that dfs is called at most once on each vertex (since it gets marked as visited)and therefore every edge is examined at most twice for an undirected graphonce from each of its end verticesand at most once in directed graphfrom its origin vertex if we let ns < be the number of vertices reachable from vertex sand ms < be the number of incident edges to those verticesa dfs starting at runs in (ns ms timeprovided the following conditions are satisfiedthe graph is represented by data structure such that creating and iterating through the incident edges(vtakes (deg( )timeand the opposite(vmethod takes ( time the adjacency list structure is one such structurebut the adjacency matrix structure is not we have way to "marka vertex or edge as exploredand to test if vertex or edge has been explored in ( time we discuss ways of implementing dfs to achieve this goal in the next section given the assumptions abovewe can solve number of interesting problems proposition let be an undirected graph with vertices and edges dfs traversal of can be performed in ( mtimeand can be used to solve the following problems in ( mtimecomputing path between two given vertices of gif one exists testing whether is connected computing spanning tree of gif is connected computing the connected components of computing cycle in gor reporting that has no cycles be directed graph with vertices and edges proposition let can be performed in ( mtimeand can be used to solve dfs traversal of the following problems in ( mtimeif one exists computing directed path between two given vertices of computing the set of vertices of that are reachable from given vertex is strongly connected testing whether or reporting that is acyclic computing directed cycle in computing the transitive closure of (see section the justification of propositions and is based on algorithms that use slightly modified versions of the dfs algorithm as subroutines we will explore some of those extensions in the remainder of this section