I am trying to perform DFS using STL stack but it is giving unexpected results

Question

This my code for DFS and it should give output like this:

Following is Depth First Traversal: 0 1 3 2 4

but it is giving the output:

Following is Depth First Traversal: 0 2 3 4 1 1 1

I am not visiting the visited element again still it is not working.

#include<bits/stdc++.h>
using namespace std;

void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void DFS(vector<int> adj[], int V, int s)
{
    stack<int> st;
    bool visited[V];
    for(int i=0; i<V;i++)
        visited[i] = false;

    visited[s] = true;
    st.push(s);
    while(st.empty()==false)
    {
        int n=st.top();
        st.pop();
        visited[n] =true;
        cout<<n<<" ";
        for(int v:adj[n])
        {
            if(visited[v]==false)
                 st.push(v);
        }
    }
}

int main()
{
    int V=5;
    vector<int> adj[V];
    addEdge(adj,0,1); 
    addEdge(adj,0,2); 
    addEdge(adj,2,3); 
    addEdge(adj,1,3); 
    addEdge(adj,1,4);
    addEdge(adj,3,4);

    cout << "Following is Depth First Traversal: "<< endl; 
    DFS(adj,V,0); 

    return 0; 
}

`vector adj[V];` -- `bool visited[V];` -- This is not legal C++. Arrays in C++ must have their size denoted by a compile time constant, not a runtime variable. Instead use `std::vector visited(V);` and `std::vector> adj(V);`. Then this: `#include` -- use the appropriate header file(s), not this one. — PaulMcKenzie, Mar 12 '21 at 06:03
*still it is not working.* -- [What is a debugger, and how can it help me diagnose problems](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Mar 12 '21 at 06:08
Also, [here is your program written in standard C++](http://coliru.stacked-crooked.com/a/1f89a48479ad3666). What you posted is not able to be compiled using an ANSI standard C++ compiler. The code at the link I posted is for those who do need an actual [mcve] of the program that actually will build. Second -- *I am not visiting the visited element again* -- This is why you need to debug your code. Just because you may not see it by looking at the code, the code is doing exactly as you wrote, even if you didn't mean it to do so. — PaulMcKenzie, Mar 12 '21 at 06:21

Hanjoung Lee · Accepted Answer · 2021-03-12T06:46:25.410

Unless there is a good reason to use an explicit stack, I would recommend to use recursion(implicit stack). However I am going to fix it least changes to your code.

There are 3 things to fix and I left comments below.

void DFS(vector<int> adj[], int V, int s)
{
    stack<int> st;
    vector<bool> visited(V, false); // 1. Don't use VLA as it is not standard

    // 2. Remove redundant first element visit marking
    st.push(s);
    while(st.empty()==false)
    {
        int n=st.top();
        st.pop();
        // 2. Check if visited since some elements may have added multiple times
        //    (Some are pushed in the stack many times but not never visited yet)
        if (visited[n]) 
            continue;
        visited[n] =true;
        cout<<n<<" ";
        // 3. Reverse the order of iteration
        for(auto v = adj[n].rbegin(); v != adj[n].rend(); ++v)
        {
            if(visited[*v]==false)
                 st.push(*v);
        }
    }
}

https://godbolt.org/z/Kz16GT

Adding some more about no. 3 - Actually 0 2 3 4 1 is a valid DFS order too. But it traverses from the reverse order of adj[n] due to the nature of Stack. So iterating reverse way will make the iteration result be 0 1 3 2 4.

I am trying to perform DFS using STL stack but it is giving unexpected results

1 Answers1