Data Structures : Graph Traversal (DFS)
Tags: algorithms, java, beginners, programming
Published: 2022-10-13 16:37:57

**Depth First Search (DFS)** is a graph traversal technique which is used to visit the nodes in a graph. 

Start from one node and visit it's adjacent node and then it's adjacent node, keep doing this until you reach the last node and then start backtracking. 
While backtracking visit the rest of the adjacent nodes in the same way.

Let's understand this with an example:
1. Consider this graph and **Node 1** as the starting point.
![traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9k7m1wj1j54hd8a1ivk2.png)

2. Now as we can see node **1** has two adjacent nodes, **2** & **3** and we can visit any one we want. In this example we'll start with **Node 2**.
![traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9vof6w3lqtycfweq17h3.png)

3. Again node **2** has two adjacent nodes and we'll pick node **5**.
![traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ttgm3lgluorb69n1paww.png)

4. This is an important part of the algorithm because there are no adjacent nodes for **5** which means we can't move forward. At this point we start backtracking and move back to node **2**.
![traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hgwhxdp971ju76pk0e5x.png)

5. We notice that node **2** has another node which we didn't visit yet so we'll do just that, we'll visit **Node 6**.

6. Again node **6** doesn't have any adjacent node so we'll backtrack to node **2** and since we have visited all the adjacent nodes of **2** we'll backtrack to node **1**. 
![traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q3yojy0sk0ugg8uatu4b.png)

7. Using the same steps we'll visit all the remaining nodes i.e. **3, 4, 8 & 7**.

8. Now you might ask that there is an edge between node **7** and **3** so do we visit it again? The answer is No because we've already visited node **3** on our way to node **7** and the same logic applies when we backtrack to node 3. We'll see how this is taken care of in the code.
![traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/en2jphrbu503ntp905ka.png)

9. So we've visited all the nodes in the graph and the path is {1, 2, 5, 6, 3, 4, 8, 7}.

Now it's time to code it up but before that I should explain the situation with already visited nodes. Since we have visited the particular node before we don't have to do that again. Now you might be wondering how do we keep track of which node we have visited and which one we haven't and the simple answer is an Array.

We simply create an array of length equal to the number of vertices in the graph and fill it with 0 or false depending on the array type you want. Now as we visit a node we simply mark that index in the array as visited by setting it as 1 or true. 

In the next dfs call we will first check if the node we are on is visited or not by simply checking the value at that index in the array. We will look at the code to better understand this.

![dfs code](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qih3cb4kovi7l93a8kih.jpeg)

Steps to sum up the code:
1. Visited array and a list are created.
2. Call the dfs on starting node.
3. Set vis[node] = true  and list.add(node).
4. For each loop on adjacency list and find the adjacent node.
5. Check if the adjacent node is visited, if not call dfs on it.
6. The path is stored in list.

Space Complexity: O(N) + O(N) + O(N) Adjacency list, Array, Auxiliary space.
                  
Time Complexity: O(N) + (2*E) Recursion call for each node + Summation of degrees.

That's it for the DFS traversal. I hope this was helpful.
Thanks for reading.