DFS traversal

In DFS Traversal, we traverse up to the deepest vertex before backtracking. Since a graph doesn’t have a root node we can select any node s a start node. The node which we visit will be marked as visited so that we do not visit the same node again

Dfs algorithm uses Stack for Traversal

DFS Algorithm

  1. Initialize stack to empty
  2. initialize all nodes of the graph as unvisited
  3. choose any node as starting node and push on to the stack and mark it as visited
  4. while the stack is not empty
    1. pop value from the stack which is at the top
    2. all the nodes that are adjacent to this poped value and which is no visited are pushed into the stack
    3. if there are no adjacent nodes then goto 4.1
DFS traversal

here initialize empty stack, and created an output array for Dfs output and a not visited array with values 0, to indicate that the node is visited or not.select node 5 as the starting node

DFS traversal 1

step 1: push 5 into the stack , pop 5 from stack add to the output array, mark 5 as visited and push adjacent nodes of 5 which are not visited to stack, here adjacent nodes of 5 is 4 so push 4 to stack

DFS traversal 2

step 2: push 4 into the stack , pop 4 from stack add to the output array, mark 4 as visited and push adjacent nodes of 4 which are not visited stack, here adjacent nodes of 4 is 3 so push 3 to stack

DFS traversal 3

step 3: push 3 into the stack , pop 3 from stack add to the output array, mark 3 as visited and push adjacent nodes of 3 which are not visited stack, here adjacent nodes of 3 is 1 so push 1 to stack

DFS traversal 4

step 4: push 1 into the stack, pop 1 from stack add to the output array, mark 1 as visited and push adjacent nodes of 1 which are not visited stack, here adjacent nodes of 1 is 2 so push 2 to stack

DFS traversal 5

step 5: push 2 into the stack, pop 2 from stack add to the output array, mark 2 as visited and push adjacent nodes of 2 which are not visited stack, here adjacent nodes of 2 which are not visited is none

Default image
Vishal Devxo
Vishal Devxo is a DevOps engineer and a Backend developer, he spends all his time for creating good tutorials with better visuals and blogging, developed some projects based on Python-Django, some hacking modules and scripts in python