时间戳

首页 > 解决方案 > 在迭代 DFS 与递归 DFS 中维护当前节点的上下文

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

问题描述

我面临一个问题，我在图中寻找一种特殊类型的节点。该算法以下列方式工作：

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 树中的任何节点是特殊的，则将当前节点标记为特殊。

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

然而，在极少数情况下，它可能会导致 Stack Overflow。

我试图弄清楚是否可以迭代地完成相同的事情。迭代方法的问题是节点的所有子节点是否都已处理的信息不容易获得。

有什么建议吗？

标签： c++recursionstackdepth-first-search

解决方案

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

推荐阅读