What seems to be wrong in this implmentation of Depth First Search?

Question

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

struct Graph
{
    int V;
    vector<list<int>> network;

    Graph(int V);
    void addEdge(int s, int v);
    void performDFS(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    network.resize(V);
}

void Graph::addEdge(int s, int v)
{
    network[s].push_back(v);
}

void Graph::performDFS(int s)
{
    vector<bool>visited;
    visited.resize(V, false);
    visited[s] = true;
    list<int> Stack;
    Stack.push_back(s);
    cout<<s<<" ";
    while(!Stack.empty())
    {
        int abc = Stack.back();
        for(int adjacent:network[abc])
        {
            if(!visited[adjacent])
            {
                visited[adjacent] = true;    
                cout<<adjacent<<" ";
                Stack.push_back(adjacent);
                abc = adjacent;
            }
        }
        Stack.pop_back();
    }
}

int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.performDFS(1);
}

The output should be 2 0 1 3, while this is giving 2 0 3 1.

The traversal starts at 2, which is marked true and printed.
Then adjacent is assigned 0, which is marked as explored, printed and pushed onto the stack. abc is changed to adjacent which is 0.
After this, adjacent should get assigned 1, since it is the only unexplored edge around 0, but for some reason, it doesn't.

Need help with this...

Just aside: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)! — πάντα ῥεῖ, May 26 '22 at 09:52
First of all maybe consider using a stack instead of a list in the DFS and adapt the code accordingly. Then see if you have a different output. — FidelCastro, May 26 '22 at 10:01
You print the element when it's inserted into the list of elements that should be visited instead of printing it, when it's actually visited. Furthermore not sure why the initial node does not count as visited immediately The output I'd expect would be `1, 2, 3, 0` or `1, 2, 0, 3` that is unless the restriction is that the node must be reached with at least 1 step. — fabian, May 26 '22 at 10:19

MT0 · Answer 1 · 2022-05-26T13:08:08.363

You need to print the vertex when it is visited (popped from the stack) rather than when you add it to the stack:

#include <vector>
#include <list>
#include <iostream>

struct Graph
{
    int V;
    std::vector<std::list<int>> network;

    Graph(int V);
    void addEdge(int s, int v);
    void performDFS(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    network.resize(V);
}

void Graph::addEdge(int s, int v)
{
    network[s].push_back(v);
}

void Graph::performDFS(int s)
{
    std::list<int> Stack;
    Stack.push_back(s);

    std::vector<bool>visited;
    visited.resize(V, false);

    while(!Stack.empty())
    {
        int v = Stack.back();
        Stack.pop_back();
        if (visited[v])
        {
            continue;
        }
        visited[v] = true;
        std::cout<< v <<" ";
        for(
            std::list<int>::reverse_iterator rit=network[v].rbegin();
            rit!=network[v].rend();
            ++rit
        )
        {
            if(!visited[*rit])
            {
                Stack.push_back(*rit);
            }
        }
    }
}

int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.performDFS(1);
}

Outputs:

1 2 0 3

Online GDB here

What seems to be wrong in this implmentation of Depth First Search?

1 Answers1