depth-first search the first traversal algorithm we consider in this section is depth-first search (dfsdepth-first search is useful for testing number of properties of graphsincluding whether there is path from one vertex to another and whether or not graph is connected depth-first search in graph is analogous to wandering in labyrinth with string and can of paint without getting lost we begin at specific starting vertex in gwhich we initialize by fixing one end of our string to and painting as "visited the vertex is now our "currentvertex--call our current vertex we then traverse by considering an (arbitraryedge (uvincident to the current vertex if the edge (uvleads us to vertex that is already visited (that ispainted)we ignore that edge ifon the other hand(uvleads to an unvisited vertex vthen we unroll our stringand go to we then paint as "visited,and make it the current vertexrepeating the computation above eventuallywe will get to "dead end,that isa current vertex such that all the edges incident to lead to vertices already visited to get out of this impassewe roll our string back upbacktracking along the edge that brought us to vgoing back to previously visited vertex we then make our current vertex and repeat the computation above for any edges incident to that we have not yet considered if all of ' incident edges lead to visited verticesthen we again roll up our string and backtrack to the vertex we came from to get to uand repeat the procedure at that vertex thuswe continue to backtrack along the path that we have traced so far until we find vertex that has yet unexplored edgestake one such edgeand continue the traversal the process terminates when our backtracking leads us back to the start vertex sand there are no more unexplored edges incident to the pseudo-code for depth-first search traversal starting at vertex (see code fragment follows our analogy with string and paint we use recursion to implement the string analogyand we assume that we have mechanism (the paint analogyto determine whether vertex or edge has been previously explored algorithm dfs( , ){we assume has already been marked as visitedinputa graph and vertex of outputa collection of vertices reachable from uwith their discovery edges for each outgoing edge (uvof do if vertex has not been visited then mark vertex as visited (via edge erecursively call dfs( ,vcode fragment the dfs algorithm