使用DFS进行拓扑排序而无需递归

问题内容：

我知道进行拓扑排序的常见方法是将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);
            }
        }
    }
}

问题答案：

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

确定何时将最后一个子节点弹出堆栈的一种方法是在堆栈上放置特殊标记，以指示特定节点的子节点开始的位置。您可以将dfs堆栈的类型更改为`vector<pair

。将bool设置为时true，表示父级；false`表示一个孩子。

当您false从堆栈中弹出“子对”（即该对中的第一个成员设置为的子对）时，您将运行当前拥有的代码，即使用for循环将其所有子级推入堆栈。for但是，在进入循环之前，您应该压入make_pair(true, node)堆栈以标记this的所有子项的开始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上的演示。

使用DFS进行拓扑排序而无需递归

微信关注