Best way to implement DFS?

general
1

Can anyone please give me a good implementation of DFS that works in a contest setting?
Right now, the implementations I know are recursive and look somewhat like this:-

void dfs(int s) {
    if (visited[s]) return;
    visited[s] = true;
    // process node s
    for (auto u: adj[s]) {
        dfs(u);
    }
}

The main problem I have with this is basically, scope.
Whenever I do the above, as I am not that comfortable with passing arrays to functions, I end up having to create the visited array and the adjacency list as globals and that means I can’t take the size of array as input and I find that somewhat tricky in some problems.

So my question is, what is a good and quick method of implementing DFS in a contest setting (in C++) so that I don’t have to deal with passing arrays to function?
What I mean by that is that the whole code for the dfs should be in the main loop itself. I am guessing that the code would have something to do with stack data structure.

Also, can someone tell me how to efficiently pass arrays to functions in c++?

TL;DR What is a good implementation of DFS that is contained in the main loop itself?

2 Likes
2

You are talking about an iterative method of DFS right?

//x is the starting vertex
stack<int>s;
vis[x]=true;
s.push(x);
while(!s.empty()){
      int v=s.top();
      s.pop();
      for(int u:adj[v]){
          if(!vis[u]){
             vis[u]=true;
             s.push(u);
     }
}
2 Likes
3

Correct me if I am wrong, but I don’t think that works.
For it to work, you would have to break after pushing u into the stack ( i think?).
This would mean that if a node has a large number of edges, the for loop would continuously have to loop upto each edge and then break.
And that would be slower than the recursive approach.

Edit: Now that I think about it, it might actually be correct.

4

No need.
Stack stores all the elements that are needed to visited this has the same time complexity as the recursive version. Note that this is just a modification of the bfs algorithm and we just used stack instead of queue.
That is all.

2 Likes