Data Structure Depth First Traversal

DATA STRUCTURE - DEPTH FIRST TRAVERSAL DATA STRUCTURE & ALGORITHMS

What is Data Structure Depth First Traversal?

A graph is traversed in a depthward motion by using a stack to go to the next vertex, by an algorithm known as Depth First Search (DFS) algorithm.

DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G.

What are the rules employed by DFS algorithm?

The following are the rules employed by the DFS algorithm:

• 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.

What are the steps in Data Structure Depth First Traversal?

The following are the steps:

Step 1 - Initialize the stack.

Step 2 - Mark S as visited and put it onto the stack. Any unvisited adjacent node is explored from S. Out of the three nodes, pick any one, preferable take in alphabetical order.

Step 3 - Mark A as visited and put it onto the stack. Any unvisited adjacent node from A are explored. Both S and D are adjacent to A but the concern is about the unvisited nodes only.

Step 4 - Visit D and mark it as visited and put onto the stack. Here, both B and C nodes are there, which are adjacent to D and both are unvisited. However, choose in an alphabetical order.

Step 5 - Choose B, mark it as visited and put onto the stack. Here B does not have any unvisited adjacent node. So, pop B from the stack.

Step 6 - Check the stack top for return to the previous node and check if it has any unvisited nodes. Here, D is found to be on the top of the stack.

Step 7 - Only unvisited adjacent node is from D is C now. So visit C, mark it as visited and put it onto the stack.

As C does not have any unvisited adjacent node so the stack is kept popping until a node with an unvisited adjacent node is found. Here, it is none and hence keep popping until stack is empty.