spanning tree of the connected component of justificationsuppose there is at least one vertex in ' connected component not visitedand let be the first unvisited vertex on some path from to (we may have wsince is the first unvisited vertex on this pathit has neighbor that was visited but when we visited uwe must have considered the edge ( , )henceit cannot be correct that is unvisited thereforethere are no unvisited vertices in ' connected component since we only mark edges when we go to unvisited verticeswe will never form cycle with discovery edgesthat isdiscovery edges form tree moreoverthis is spanning tree becauseas we have just seenthe depth-first search visits each vertex in the connected component of in terms of its running timedepth-first search is an efficient method for traversing graph note that dfs is called exactly once on each vertexand that every edge is examined exactly twiceonce from each of its end vertices thusif vertices and edges are in the connected component of vertex sa dfs starting at runs in ( timeprovided the following conditions are satisfiedthe graph is represented by data structure such that creating and iterating through the incidentedges(viterable collection takes (degree( )timeand the opposite( ,emethod 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 graph with vertices and edges represented with an adjacency list dfs traversal of can be performed in ( mtimeand can be used to solve the following problems in ( mtimetesting whether is connected computing spanning tree of gif is connected computing the connected components of computing path between two given vertices of gif it exists