An Interest In:
Web News this Week
- April 18, 2024
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
- April 13, 2024
- April 12, 2024
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
Original Link: https://dev.to/anurag31oct/dfs-in-one-shot-53dl
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To