在迭代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）您无需检查是否已经访问过节点-也许可以加快它的速度。 （编辑：我看不懂）