在迭代 DFS 与递归 DFS 中维护当前节点的上下文

Question

我遇到了一个问题，我要在图中寻找一种特殊类型的节点。该算法按以下方式工作：

bool findSpecial(Node n)
{
    if(isSpecial(n))
        return true;

    bool isSpecial = false;
    vector<Node> childs = getChildren(n);
    foreach(child, childs)
    {
       isSpecial |= findSpecial(child);
    }

    if(isSpecial)
      markCurrentNodeSpecial(n);

    return isSpecial;
}

以上是算法的模板，假设输入是DAG。它在图中寻找特殊节点，如果 DFS 树中的任何节点是特殊的，则将当前节点标记为特殊节点。

算法基本上是在任何可到达的地方填充这个特殊属性。

然而，在极少数情况下，它可能会导致堆栈溢出。

我想知道是否可以迭代地完成同样的事情。迭代方法的问题是一个节点的所有子节点是否都被处理的信息并不容易获得。

有什么建议吗？

Answer 1

1) 最简单的解决方案 - std::stack<Node> 可行吗？你应该让它像程序堆栈一样工作 - 将起始 Node 推到那里，然后弹出一个节点，检查它是否特殊，如果不是 - 推它的子节点，重复。

2) 你不检查你是否已经访问过一个节点 - 也许你可以加快一点速度。（编辑：我看不懂）

更新：是的，这是一只有趣的野兽。这段代码怎么样？虽然我没有测试它，但主要思想应该可行：将访问分为两个步骤 - 递归之前和之后。

struct StackNodeEntry
{
    Node cur;
    optional<Node> parent;

    enum class Pos
    {
        before_recursion, after_recursion
    } pos;
};

bool findSpecial(Node root)
{
    stack<StackNodeEntry> stack;

    stack.push({ root, {}, StackNodeEntry::Pos::before_recursion });

    while (!stack.empty())
    {
        auto& e = stack.top();

        switch (e.pos)
        {
        case StackNodeEntry::Pos::before_recursion:
            if (isSpecial(e.cur))
            {
                if (e.parent)
                    markCurrentNodeSpecial(*e.parent);
                stack.pop();
                break;
            }

            for (auto n : getChildren(e.cur))
                stack.push({ n, e.cur, StackNodeEntry::Pos::before_recursion });
            e.pos = StackNodeEntry::Pos::after_recursion;
            break;

        case StackNodeEntry::Pos::after_recursion:

            if (isSpecial(e.cur))
            {
                if (e.parent)
                    markCurrentNodeSpecial(*e.parent);
            }
            stack.pop(); // don't use e below this line
            break;
        }
    }

    return isSpecial(root);
}

在迭代 DFS 与递归 DFS 中维护当前节点的上下文

Maintaining context of current node in a iterative DFS vs a recursive DFS

c++

recursion

stack

depth-first-search