Iterative Depth First Search in Data Structure | DFS (Iterative) | C++ Java Python

[@MrSun8080]

I honestly never understood dfs and backtracking mechanisms but now that I watched your videos about dfs I'm finally getting how it works and I'm able to solve dfs questions that I could not solve before.

[@KnowledgeCenter]

That's great to hear.

[@israkulhaquetusher3256]

Please try to add some problems according to the topic so that after learning we can practice.

[@KnowledgeCenter]

Ok.

[@prabhatchanchal]

Nice explanation...

[@KnowledgeCenter]

Thanks

[@noushadkhan360]

What's the use of for loop in dfs

[@KnowledgeCenter]

I assume you are talking about : for all v: adj[u]{....} From a given node u, we can next go to one of its neighbors. adj[u] is a list containing all the neighbors. We have to explore all nodes going as deep as we can. So, first we pick one of the neighbors v, then go as deep as we can. Then after all options are exhausted, we check next neighbor, if its unvisited, we visit that and continue. We do that for all the neighbors. So, for loop.

[@sayantaniguha8519]

The iterative code for DFS is wrong

[@KnowledgeCenter]

What's wrong with the code?

[@sayantaniguha8519]

@@KnowledgeCenter ​ @Knowledge Center No the iterative answer is wrong. GFG Practice Platform agrees with me Submit your iterative soln. there / u will get wrong answer

[@KnowledgeCenter]

Not sure how, it is wrong. Please follow the code given in this video description: github.com/KnowledgeCenterKZbin/Graphs/blob/master/DFS GFG may be using different function signature. The code given in the video link returns correct output. Every site will have slightly different function signatures. So, you need to modify the code to submit there.

[@sayantaniguha8519]

@@KnowledgeCenter Yes I did / I am still getting incorrect /I have mailed u details about this / Can u submit your solution on GFG Practice & share?

[@KnowledgeCenter]

If we start DFS from node 0, It can first go to any of the three neighbors - 1, 2 or 3. Depending on which neighbor it visits first dfs() will be different. So, some of the possible dfs orders are: Visit 1 then 2 then 3 : 0, 1, 2, 4, 3 Visit 1 then 3 then 2 : 0, 1, 3, 2, 4 Visit 2 then 1 then 3 : 0, 2, 4, 1, 3 Visit 2 then 3 then 1 : 0, 2, 4, 3, 1 Visit 3 then 1 then 2 : 0, 3, 1, 2, 4 Visit 3 then 2 then 1 : 0, 3, 2, 4, 1 All of these are correct dfs orders.

[@maheiramkhan]

Why did we not do similarly for BFS?

[@KnowledgeCenter]

In iterative implementation of BFS, we use a Queue instead of a Stack, because there the goal is to print a node u, then all its immediate neighbours of u, then all the neighbors 2 units distance from u, and so on.

[@swaw11]

The code is wrong. If you mark all the adjacent nodes visited, then the child nodes will not be able to go visit some node in a depth-first way because it is already marked as visited. while (!stack.empty()) { int u = S.top(); S.pop(); if (!visited[u]) { cout

[@KnowledgeCenter]

Here traversal operation denotes the cout/print operation. In some custom application, cout will be replaced by any other operation. You will notice that we are marking a node visited after pushing it to the stack. But, we are printing it to console only after we pop out the node. So, first we push all neighbours of a node u to the stack, mark them visited, then pop() one of the neighbours, say v1, and print it (u --> v1). Now we push all unvisited neighbours of v1 to stack. So, next time we pop(), it will be some neighbour w1 of v1. So, next w1 will be printed, and not other neighbours of earlier node u. So, u --> v1 --> w1. Once, we exhaust all the possibilites, then only the next neighor v2 of our original node u will be printed.

[@sayantaniguha8519]

​@@KnowledgeCenter The iterative code for DFS is wrong