使用迭代而非递归进行拓扑排序

Question

我最初使用递归解决了拓扑排序问题：

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) {
    visited[v] = true;
    node* curr = adjList[v];

    while (curr != NULL) {
        if(!visited[curr->val]) {
            dfs(curr->val, visited, adjList, myStack);
        }
        curr = curr->next;
    }
    myStack.push(v);
}

看起来对我的目的很有效。但是我在将其转化为迭代解决方案时遇到了问题。以下是我的尝试：

void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) {
    std::stack<int> recursion;
    visited[v] = true;

    recursion.push(v);

    while( !recursion.empty() ) {
        v = recursion.top();
        recursion.pop();
        node* curr = adjList[v];

        myStack.push(v);

        while (curr != NULL) {
            if(!visited[curr->val]) {
                visited[curr->val] = true;
                recursion.push(curr->val);
            }
            curr = curr->next;
        }
    }
}

但是排序完全混乱了！我认为这可能是由于我的myStack.push(v)的位置，但我不知道如何解决。任何帮助将不胜感激。

- Jon

---

我在过去几天里思考了一下，通常的技巧是反转递归退出条件，并将其用作非递归函数的 while 条件。然后，我推测，您可以保留大部分旧逻辑。 - BitTickler

@BitTickler 你是什么意思？ - Jon

主要区别在于，在递归中，您有不同状态的“visited”，而在迭代版本中，您仅修改一个这样的列表，并在回溯时取消设置“visited”。 - SpamBot

Answer 1

我认为我解决了自己的问题。本质上，您可以通过按节点完成时间对节点进行排序来获得拓扑顺序。但是，我们可以将此保持为O（n），而不是进行排序并获得O（nlogn）解决方案。当你完成一个节点时，我们可以弹出节点的唯一标识符并将其压入栈中，而不是记录它的完成时间。由于在我的情况下只涉及正节点，因此使唯一标识符简单地成为该节点值的负数即可。因此，如果我们连续弹出堆栈，我们将获得我们的拓扑顺序。

 void dfs(int v, bool visited[], node* adjList[], std::stack<int> &myStack) {
     std::stack<int> recursion;
     visited[v] = true;
     recursion.push(v);

     while( !recursion.empty() ) {
        v = recursion.top();
        recursion.pop();

        //A dummy node to denote finish order (e.g. topological order)
        if (v < 0) {
            myStack.push(v * -1);
        } else {
            node* curr = adjList[v];
            recursion.push(v * -1);

             while (curr != NULL) {
                if(!visited[curr->val]) {
                    visited[curr->val] = true;
                    recursion.push(curr->val);
                }
                curr = curr->next;
            }
        }
    }
}

- Jon

---

这个答案对我来说非常有效。你的符号翻转技巧真的很聪明，取模时所有条目都大于0，这绝对是我的情况。谢谢。 - riccardoventrella