在深度搜索的暗示中似乎有什么问题？

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

输出应为2 0 1 3，同时给出2 0 3 1。

1. 遍历开始于2，标记为真实并打印。
2. 然后分配了相邻的0，该0被标记为探索，打印并将其推到堆栈上。 ABC已更改为0。
3. 在此之后，相邻应分配1，因为它是唯一未探索的边缘，但由于某种原因而不是。

需要帮助...

Answer 1

您需要在访问该顶点（从堆栈中弹出），而不是将其添加到堆栈时：

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

输出：输出：

  1 2 0 3
 

在线gdb 在这里