将基于DFS的递归拓扑排序转换为非递归算法（不丢失周期检测） [英] Transforming recursive DFS-based topological sort into a non-recursive algorithm (without losing cycle detection)

问题描述

这是维基百科中用于拓扑排序的伪代码：

Here is a pseudocode for topological sort from Wikipedia:

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

我想以非递归方式编写它，而又不会丢失cicle检测。

I want to write it non-recursively without losing cicle detection.

问题是我不知道该怎么做，我已经想到了许多方法。基本上，问题是执行DFS，但要记住当前路径（它对应于上述伪代码中的临时标记某些节点）。因此，使用堆栈的传统方法无法提供任何好处，因为使用堆栈（并将每个节点的邻居放置在其中）时，即使我在不确定的未来中看到它们，也将节点放置在其中，而我只想跟踪节点在我当前的路径上（我看到它就像是走在迷宫中，留下了一条留在我身后的线-当我看到一个死胡同时，我回头并在这样做的任何时候包裹胎面我想记起线程上放着节点的节点以及线程已至少出现过一次的节点）的时间。有什么秘诀会指出正确的方向吗？我的意思是-我应该考虑使用2个堆栈而不是1个堆栈，也许是其他数据结构吗？

The problem is I don't know how to do that and I thought of many approaches already. Basically the problem is to do DFS but with remembering the "current path" (it corresponds to "temporary marking" certain nodes in pseudocode above). So traditional approach with a stack gives me nothing because when using a stack (and putting neighbors of every node in it) I'm putting nodes there even though I will see them "in the undetermined future" and I only want to keep track of nodes "on my current path" (I see it as walking through a maze with a thread I'm leaving behind me - when I see a dead end, I turn back and "wrap the tread" when doing that and at any point in time I want to remember nodes "with thread lying on them" and nodes on which the thread has been at least once). Any tips that would point me in the right direction? I mean - should I think of using 2 stacks instead of 1, maybe some other data structure?

或者此算法可能还可以，我应该将其保留为递归形式。我只担心要为足够大的图形超出递归深度。

Or maybe this algorithm is OK and I should leave it in its recursive form. I'm only worrying about exceeding the "recursion depth" for sufficiently large graphs.

推荐答案

很显然，您会使用堆栈但是无论如何您都不会放置所有相邻的节点：无论如何，这都会产生一个具有错误的大小复杂度的DFS（假设不平行的边缘，节点数量将是平方，否则可能会更糟）。而是将当前节点与指示下一个要访问的节点的状态一起存储。您总是会从堆栈的顶部开始工作，例如：

Obviously, you'd use a stack but you wouldn't put all adjacent nodes anyway: that would yield a DFS with the wrong size complexity anyway (it would be quadratic in the number of nodes assuming non-parallel edges, otherwise potentially worse). Instead, you'd store the current node together with a state indicating the next node to be visited. You'd always work off the stack's top, i.e., something like this:

std::stack<std::pair<node, iterator> stack;
stack.push(std::make_pair(root, root.begin()));
while (!stack.empty()) {
    std::pair<node, iterator>& top = stack.top();
    if (top.second == top.first.begin()) {
        mark(top.first);
        // do whatever needs to be done upon first visit
    }
    while (top.second != top.first.end() && is_marked(*top.second)) {
        ++top.second;
    }
    if (top.second != top.first.end()) {
        node next = *top.second;
        ++top.second;
        stack.push(std::make_pair(next, next.first());
    }
    else {
        stack.pop();
    }
}

此代码假定节点具有 begin（）和 end（）产生合适的迭代器来迭代相邻的节点，沿着这些线的东西，当然可能存在通过边的间接访问，当然也存在。有一些功能可以访问节点的标记。在更现实的实现中，可能会使用BGL属性映射。是否可以使用 std :: stack< T> 表示堆栈的方式取决于是否需要访问堆栈上的当前节点： std :: stack 不提供这种访问权限，但是，创建一个基于任何STL序列容器的合适堆栈实现。

This code assumes that nodes have a begin() and end() yielding suitable iterators to iterate over adjacent nodes. Something along those lines, possibly with an indirection via edges will certainly exist. It also assumes that there are functions available to access a node's mark. In a more realistic imlementation that would probably use something a BGL property map. Whether a std::stack<T> can be used to respresent the stack depends on whether the nodes currently on the stack need to be accessed: std::stack doesn't provide such access. However, it is trivial to create a suitable stack implementation based on any of the STL sequence containers.

这篇关于将基于DFS的递归拓扑排序转换为非递归算法（不丢失周期检测）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！