c++ - 图的逆序遍历

Question

这个问题是我从 DFS 图遍历算法中得到的奇怪行为的结果。我试图实现 DFS，这是我的代码:

#include<iostream>
#include<stack>
#include<vector>
#include<map>

using namespace std;
map<int,bool> discovered;

map< int , vector<int> > graph {
    {1,{2,3}},
    {2,{1,4,5}},
    {3,{1}},
    {4,{2}},
    {5,{2}}
};

vector <int> visited;
void clear_graph(){
for( map<int,bool>:: iterator iter = discovered.begin(); iter != discovered.end(); iter++)
    discovered[iter->first] = false;
}


void dfs( int start ) {    
    int current;
    int next;
    unsigned int i;
    stack <int> vertices;
    discovered[start] = true;
    vertices.push(start);

    while (!vertices.empty()){
        current = vertices.top();
        visited.push_back(current);
        vertices.pop();
        for( i = 0 ; i<graph[current].size() ; i++){
            next = graph[current][i];
            if ( !discovered[next] ){
                discovered[next] = true;
                vertices.push(next);
            }
        }
    }
}

int main() {    
    clear_graph();
    int start = 1;
    dfs(start);

    vector<int> ::iterator vi;
    for( vi=visited.begin(); vi!=visited.end();vi++)
        cout<<*vi<<" ";

    return 0;
}

这是我正在考虑的图表:

图中的输出是:1->2->4->5->3但我得到的输出是:1->3->2->5->4

我可以观察到它也是一个有效的 DFS 遍历，但在从右到左的排序中，为什么会这样？如果错了，我的代码中的哪一部分出错了？在需要 DFS 遍历的情况下，单个图的这种多次遍历不会产生不正确的结果吗？

Answer 1

只是算法不同的问题。

如果你递归地做，你会在备份到 3 之前完全迭代 2，因此 1->2->4->5->3。如果您迭代执行此操作，您将以相反的顺序访问邻居，因此您将首先完全迭代 3，因此 1->3->2->5->4。您的算法仍然是正确的深度优先搜索算法，只是与图像碰巧使用的算法不同。

如果您想保留迭代解决方案但得到与递归解决方案相同的结果，您可以反转顺序。变化:

next = graph[current][i];

到:

next = graph[current][graph[current].size() - i - 1];