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
Top comments (0)