使用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,表示父; false表示一个孩子.

当您false从堆栈中弹出一个"子对"(即将该对中的第一个成员设置为)时,您运行当前拥有的代码,即将所有子代素一起推入堆栈for.for但是,在进入循环之前,您应该按下make_pair(true, node)堆栈以标记所有子项的开头node.

当您从堆栈中弹出"父对"时,将父索引推送到postOrder,然后继续:

vector<bool> visited(MAX);
stack<pair<bool,int> > dfs;
stack<int> postOrder;
vector<int> newVec;
vector<int>::iterator it;
vector<vector<int> > graph;
for(int i=0;i<MAX;i++){
    if(visited[i]==false){
        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;
        }
        visited[node.second]=true;
        dfs.push(make_pair(true, node.second));
        newVec=graph[node.second]; //vector of neighboors
        for(it=newVec.begin();it!=newVec.end();it++){
            int son=*it;
            if(visited[son]==false){
                dfs.push(make_pair(false, son));
            }
        }
    }
}

在ideone上演示.