Depth First Traversal

When a dead end occurs in any iteration, the Depth First Search (DFS) method traverses a network in a depthward motion and uses a stack to remember to acquire the next vertex to start a search.

Depth First Travesal

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to C. It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
  • Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
  • Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
StepTraversalDescription
1Depth First Search Step OneInitialize the stack.
2Depth First Search Step TwoMark S as visited and put it onto the stack. Explore any unvisited adjacent node from S. We have three nodes and we can pick any of them. For this example, we shall take the node in an alphabetical order.
3Depth First Search Step ThreeMark A as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both S and D are adjacent to A but we are concerned for unvisited nodes only.
4Depth First Search Step FourVisit D and mark it as visited and put onto the stack. Here, we have B and C nodes, which are adjacent to D and both are unvisited. However, we shall again choose in an alphabetical order.
5Depth First Search Step FiveWe choose B, mark it as visited and put onto the stack. Here B does not have any unvisited adjacent node. So, we pop B from the stack.
6Depth First Search Step SixWe check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find D to be on the top of the stack.
7Depth First Search Step SevenOnly unvisited adjacent node is from D is C now. So we visit C, mark it as visited and put it onto the stack.
Because C has no unvisited neighboring nodes, we continue to pop the stack until we discover a node with an unvisited adjacent node. There are none in this situation, therefore we keep popping until the stack is empty.
0

1 thought on “Depth First Traversal”

Leave a Comment

Your email address will not be published. Required fields are marked *

eight + 14 =