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

问题描述

这里是维基百科拓扑排序的伪代码：

Here is a pseudo-code 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，但是重新描绘当前路径（它对应于临时标记上面的伪代码中的某些节点）。所以传统的堆栈方法没有什么，因为当使用堆栈（并把它的每个节点的邻居），我把节点放在那里，虽然我会看到他们在未来的未来，我只想跟踪节点在我的当前路径（我认为它走过一个迷宫与一个线程，我离开behing我 - 当我看到一个死胡同，我回头，包裹在踏板，当这样做，时间我想记住节点线程躺在他们和节点上的线程已经至少一次）。任何提示，会指向我的方向正确？我的意思是 - 我应该考虑使用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 rememering the "current path" (it coressponds to "temporary marking" certain nodes in pseudo-code above). So traditional approach with a stack gives me nothing because when using a stack (and putting neighbours 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 behing 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 code>和 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屋！