c++ - 使用不递归的 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);
            }
        }
    }
}

Answer 1

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

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

当你从堆栈中弹出一个“子对”(即一对中的第一个成员设置为 false )时，你运行你当前拥有的代码，即将他们的所有 child 插入堆栈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));
            }
        }
    }
}

Demo on ideone.