specified goal state by moving between states only through the connections typicallythe start and goal states are not directly connected to solve this problemthe vertices of the graph must be searched in some organized manner graph traversal algorithms typically begin with start vertex and attempt to visit the remaining vertices from there graph traversals must deal with number of troublesome cases firstit may not be possible to reach all vertices from the start vertex this occurs when the graph is not connected secondthe graph may contain cyclesand we must make sure that cycles do not cause the algorithm to go into an infinite loop graph traversal algorithms can solve both of these problems by maintaining mark bit for each vertex on the graph at the beginning of the algorithmthe mark bit for all vertices is cleared the mark bit for vertex is set when the vertex is first visited during the traversal if marked vertex is encountered during traversalit is not visited second time this keeps the program from going into an infinite loop when it encounters cycle once the traversal algorithm completeswe can check to see if all vertices have been processed by checking the mark bit array if not all vertices are markedwe can continue the traversal from another unmarked vertex note that this process works regardless of whether the graph is directed or undirected to ensure visiting all verticesgraphtraverse could be called as follows on graph gvoid graphtraverse(graph gint vfor ( = < () ++ setmark(vunvisited)/initialize for ( = < () ++if ( getmark( =unvisiteddotraverse(gv)function "dotraversemight be implemented by using one of the graph traversals described in this section depth-first search the first method of organized graph traversal is called depth-first search (dfswhenever vertex is visited during the searchdfs will recursively visit all of ' unvisited neighbors equivalentlydfs will add all edges leading out of to stack the next vertex to be visited is determined by popping the stack and following that edge the effect is to follow one branch through the graph to its conclusionthen it will back up and follow another branchand so on the dfs process can be used to define depth-first search tree this tree is composed of