DFS in one shot!

We use DFS in Tree and Graph.

You must know **recursion **before jumping into DFS

• Recursion

Now to write a recursive function there are only 2 things-

`int recur(int n) {
if(n == 0) // known as base case

return n-1; // operation you want to perform!
`

Now see DFS as a recursive function-

What we do in Graph using DFS?
_ -> We just visit each node of the graph_

So in this case-

When should we stop? What is the base case?

-> When we encounter the same cell, visited earlier we should stop.

So, if (Vis[currnode] == True), means we have already visited the node, we should stop.

So code will be like this-

Void dfs(int currnode) {
if(Vis[currnode] == true) return;
}

step 1 is done--

now step 2 of recursion is to write what you want to perform-

we want to traverse the graph.
How we can do this?
-> By going from one cell to other-

So code will be like this-

for (auto it : adj[currnode]) {  // go to all it's neighbours
  if(!vis[it]) {              // check if it's been visited already
     cout << it << ' ';       // print it
     vis[it] = true; // make sure mark currentnode visited = true
     dfs(it);        // call the dfs again(recursion)
}

so final code will be like this-

Void dfs(int currnode) {

**// step 1**

if(Vis[currnode] == true) return;

**// step 2**

for (auto it : adj[currnode]) {  // go to all it's neighbours
  if(!vis[it]) {              // check if it's been visited already
     cout << it << ' ';       // print it
     vis[it] = true; // make sure mark currentnode visited = true
     dfs(it);        // call the dfs again(recursion)
}

}

Keep it in mind: Your output will be different, if you choose different node as your currentnode