fig path from vertex to vertex graphthere seems to be only one choice in most cases howeverwhen the search reaches vertex we must choose between two edges one edge takes us back to vertex which we have already visited the other edge takes us closer to the final path another choice is made at vertex if the edge to is wrongly examinedwe must have way of backing up and trying the other edge to vertex searching graph in this manner is also called depth first searchas first discussed in chap and requires the ability to backtrack consider when vertex is encountered if choice is made to go to vertex we must be able to back up to fix that choice and go to vertex instead stack data structure or recursion handles the backtracking depth first search must also avoid possible cycles within the graph the avoidance of cycles is accomplished by maintaining set of visited vertices when vertex is visitedit is added to the visited set if vertex is in the visited setthen it is not examined again later in the search should cycle take the search back to the same vertex an iterative ( non-recursivegraph depth first search algorithm begins by initializing the visited set to the empty set and by creating stack for backtracking the start vertex is pushed onto the stack to begin the algorithm steps similar to those taken in sect are executed to find the goal this code is pseudo-codebut presents the necessary details iterative depth first search of graph def graphdfs(gstartgoal) ( ,eis the graph with verticesvand edgese , stack stack(visited set(stack push(start while not stack isempty() vertex is popped from the stack this is called the current vertex current stack pop(this copy belongs to 'acha