# What is DFS?

Depth First Search or in short DFS is an algorithm to traverse the graph by exploring its nodes in a depth ward way. It is like going to the extreme way possible each time, and if you can not go farther, returning to the node you started from and trying to explore further, until all the nodes are visited. Here We will see how we can perform DFS Traversal using a recursive function.

###### DFS Graph Traversal by Recursion | PrepInsta ## DFS Graph Traversal using Adjacency list

If we represent the graph by Adjacency list, we have two ways to traverse the whole graph. Either we can reach all the nodes recursively, or we can use a stack data structure to keep track all the last visited node. Recursion does use the stack, as functions are called by stack memory which operates the same way a stack data structure does.

Prerequisites: Graph Representation by Adjacency list

### DFS Graph Traversal by Recursion

Here we are about to write a function to do these following things;

• Starting from the node we want to start traversing (Lets say i-th node)
• Putting the i-th node in the argument.
• Marking the i-th as node visited.
• Defining the function that goes to the next possible nodes from i-th node.
• If cannot go farther, return.

#### Explanation

Let us say we have 6 nodes, and they are 0,1,2,3,4,5 respectively. And There are 7 edges, in between the following nodes : (1,2), (2,3), (1,0), (1,5), (5,2), (5,4), (0,3). So,

• Starting traversal from node 0.
• from node 0,  we can directly visit the nodes namely 1 and 3. So calls the function with 1 and 3 in arguments respectively.
• from node 1,  we can directly visit the nodes namely 0, 2, 5, but the 0 is visited. So it recursively calls for the rests, and so on.

### The code to implement this:

#include<bits/stdc++.h>
using namespace std;
int *vis; // Declaring the array globally so that we can use it by any function and manipulate.
// Declaring it dynamically as we don’t know the number of vertices.
void dfs(int ivector<int*Adj) // The recursive function
{
if(vis[i]) {return;} // If the node is visited, return
vis[i]=1;
cout<<“Visiting the node named “<<i<<endl;
for(int j=0;j<Adj[i].size();j++) // tracking all the directly connected nodes through adjacency list
}
{
}
int main()
{
int v=6; // Declaring number of vertices

vis = new int[v];
for(int i=0;i<v;i++) // Marking all nodes as unvisited in the start
vis[i]=0;