图的逆序遍历

Question

这个问题是我从 DFS 图遍历中得到的奇怪行为的结果 algorithm.i 试图实现 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];

Answer 2

你的遍历是相反的，因为你使用了堆栈数据结构，它以与它们被推入堆栈的方式相反的顺序（后进先出）弹出项目。您将顶点向前推入堆栈，因此您从堆栈中向后获取它们。

以下是解释遍历反转的原因的内联注释：

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

    while (!vertices.empty()){
        // here you pop vertices from the stack in the reverse order of how
        // the vertices were pushed into the stack
        current = vertices.top();
        visited.push_back(current);
        vertices.pop();
        // here you traverse the vertices forward
        for( i = 0 ; i<graph[current].size() ; i++){
            next = graph[current][i];
            if ( !discovered[next] ){
                discovered[next] = true;
                // here you push vertices into the stack
                vertices.push(next);
            }
        }
    }
}

Answer 3

您正在按从左到右的顺序将子节点压入堆栈。结果，将首先弹出并处理正确的节点。要按从左到右的顺序遍历子项，请将 for 循环更改为：

for (int i = graph[current].size()-1; i >= 0; --i)

图的逆序遍历

reverse ordered traversal of a graph

c++

stl

graph-theory