 # Best way to implement DFS?

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

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

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.

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