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; 
}

Answer 1

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.