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.

Depth First Traversal

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.

DFS Step one

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.

DFS Step Two

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.

DFS Step Three

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.

DFS Step Four

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.

DFS Step Five

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.

DFS Step Six

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.

DFS Step Seven

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


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics