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

To understand about the implementation of Data Structure Depth First Traversal algorithm in C programming language, click here