DFS is one of the techniques to process the vertices or edges of a graph in a systematic order.The procedure is as below
- Visit a vertex of a graph arbitrarily and mark it as being visited
- Visit any unvisited vertex which are adjacent to previous one
- Repeat the step2 until no adjacent vertex is left out for a particular vertex
- Go back to one vertex before the dead-end vertex and try to find any unvisited vertex and repeat the peocess if so
- The algorithm halts when the starting vertex becomes the dead-end and by this time,all the vertices in that connected component of a graph are visited
- If the graph containd still unvisited vertices reapply the above peocedure by choosing any arbitrary vertex
- To impement the operation of DFS ,we will use stack
- When a vertex is reached for the first time,it is pushed into the stack
- When it becomes the dead-end ,we pop-up it
- Sometimes the DFS forest is used for illustrating DFS traversal
- In DFS forest the starting vertex of DFS traversal acts as a root of first tree
- Whenever a new unvisited node is encountered it is put as child to the vertex from which it is being searched
- The edge connecting two such nodes is called as tree edge
- In this process we may get an edge from a particular node to a previously visited node,which is not its parent
- Such an edge is called as back-edge
