使用DFS没有递归拓扑排序 [英] Topological sort using DFS without recursion

问题描述

我知道做一个拓扑排序的常用方法是使用DFS递归。但是，使用你会怎么办呢堆栈＆LT; INT＆GT; 而不是递归？我需要得到逆转后的订单，但我有点卡住了：

I know the common way to do a topological sort is using DFS with recursion. But how would you do it using stack<int> instead of recursion? I need to obtain the reversed post-order but I'm kinda stuck:

图为一个矢量＆lt;矢量＆lt; INT＆GT; ＆GT; 邻接表

下面是我想使用的拓扑排序的DFS

The following is the DFS which I want to use for topological sort

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);
            }
        }
    }
}

谢谢！

推荐答案

为了构建后序列表，你需要知道的时候，你的算法处理完节点的最后一个子 K 。

In order to construct the postOrder list you need to know the time when your algorithm has finished processing the last child of node k.

要找出当你已经出现了最后一个孩子从堆栈是把堆栈上的特殊标记，表明斑点，其中一个特定节点的孩子开始的一种方法。你可以改变的类型，你的 DFS 堆到矢量＆lt;对＆LT; BOOL，INT＆GT; ＆GT; 。当布尔设置为真，表示父母; 假表示一个孩子。

One way to figure out when you have popped the last child off the stack is to put special marks on the stack to indicate spots where the children of a particular node are starting. You could change the type of your dfs stack to vector<pair<bool,int> >. When the bool is set to true, it indicates a parent; false indicates a child.

当你弹出一个孩子对（即一个具有对置的第一个成员假）从堆栈，运行code表示您当前有，即按他们的孩子到堆栈中有你的为循环。在进入为循环，但是，你应该推 make_pair（真，节点）入堆栈，以纪念开始这个节点的所有孩子。

When you pop a "child pair" (i.e. one with the first member of the pair set to false) off the stack, you run the code that you currently have, i.e. push all their children onto the stack with your for loop. Before entering the for loop, however, you should push make_pair(true, node) onto the stack to mark the beginning of all children of this node.

当你弹出一个父对关栈，你推父索引到后序，并继续前进：

When you pop a "parent pair" off the stack, you push the parent index onto the postOrder, and move on:

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没有递归拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！