使用没有递归的 DFS 进行拓扑排序

Question

我知道进行拓扑排序的常用方法是使用带有递归的 DFS。但是你会如何使用 stack<int> 而不是递归呢？我需要获得相反的后订单，但我有点卡住了：

该图是一个 vector<vector<int> > 邻接表

以下是我要用于拓扑排序的 DFS

 bool visited[MAX]={0};
stack<int> dfs, postOrder;
vector<int> newVec;
vector<int>::iterator it;

for(int i=0;i<MAX;i++){
    if(visited[i]==false){
        dfs.push(i);
    }
    while(!dfs.empty()){
        int node=dfs.top();
        dfs.pop();
        visited[node]=true;
        newVec=graph[node]; //vector of neighboors
        for(it=newVec.begin();it!=newVec.end();it++){
            int son=*it;
            if(visited[son]==false){
                dfs.push(son);
            }
        }
    }
}

原文由 fersarr 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

为了构造 postOrder 列表，您需要知道算法完成处理节点 k 的最后一个子节点的时间。

确定何时将最后一个子节点从堆栈中弹出的一种方法是在堆栈上放置特殊标记以指示特定节点的子节点开始的位置。您可以将 dfs 堆栈的类型更改为 vector<pair<bool,int>> 。当 bool 设置为 true 时，表示父级； false 表示孩子。

当您从堆栈中弹出一个“子对”（即该对的第一个成员设置为 false ）时，您运行您当前拥有的代码，即将他们所有的孩子推入堆栈你的 for 循环。但是，在进入 for 循环之前，您应该将 make_pair(true, node) 压入堆栈以标记此 node 的所有子级的开始。

当您从堆栈中弹出“父对”时，您将父索引推送到 postOrder ，然后继续：

 vector<vector<int> > graph;
vector<bool> visited(max);
stack<pair<bool,int>> dfs;
stack<int> postOrder;
for(int i=0 ; i < max ; i++){
    if(!visited[i]){
        dfs.push(make_pair(false,i));
    }
    while(!dfs.empty()){
        pair<bool,int> node=dfs.top();
        dfs.pop();
        if (node.first) {
            postOrder.push(node.second);
            continue;
        }
        if (visited[node.second]) {
            continue;
        }
        visited[node.second]=true;
        dfs.push(make_pair(true, node.second));
        const auto& newVec=graph[node.second]; //vector of neighboors
        for(const auto son: newVec){
            if(!visited[son]){
                dfs.push(make_pair(false, son));
            }
        }
    }
}

ideone 上的演示。

原文由 Sergey Kalinichenko 发布，翻译遵循 CC BY-SA 4.0 许可协议