![depth first search dfs](https://techindetail.com/wp-content/uploads/2021/09/depth-first-search.png)
Depth First Search DFS
Depth First Traversal or Depth First Search (DFS) algorithm traverses a Graph in a depth manner and uses a stack to store the visited nodes.
DFS traversal proceeds level by level, DFS follows a path from the starting node to an ending node, then another path from the start to the end, until all the nodes are visited.
A path is set until no unvisited nodes remain, and then the algorithm selects the last visited node that has unvisited adjacent nodes.
DFS Algorithm
- Select a node, follow the path to end.
- Select another node follow its path.
- Visit the adjacent unvisited nodes. Push it in a stack.
- If no adjacent node is found, pop up a vertex from the stack.
- Repeat the steps until the stack is empty.
DFS Example 1
![dfs example solved](https://techindetail.com/wp-content/uploads/2021/09/depth-first-search-img.png)
The depth first traversal of the graph above is in the order 1, 2, 4, 8, 7, 3, 6.
A path is selected until no unvisited nodes remain reachable, then the traversal goes back to the last node that was visited that has unvisited adjacent nodes.
A valid result of depth first search of the graph above is 1, 3, 6, 7, 8, 2, 5, 4.
DFS Example 2
For this graph, we can start with vertex 1. Now to initiate depth first search, an adjacent vertex is selected.
![dfs example steps](https://techindetail.com/wp-content/uploads/2021/09/dfs-traversal-steps.png.webp)
Let 2, 3, 8, are adjacent vertices of vertex 1. We can select any vertex from these vertices let us select vertex 2, now all the adjacent vertices of vertex 2 are processed and visited, next vertex 3 is selected and all its adjacent vertices are visited.
The algorithm runs until all the vertices are visited. We must set a flag for all the visited nodes, in order to not traverse the vertex a second time.
Depth First Search Flowchart
![dfs flowchart](https://techindetail.com/wp-content/uploads/2021/09/flowchat-depth-first-traversal-648x720.png.webp)
See Also: Breadth First Search (BFS)