# DFS traversal

Last Updated on

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

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

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

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

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

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

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

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