Поддержание контекста текущего узла в итерационном DFS по сравнению с рекурсивными DFS ⇐ C++

[Anonymous]

Я сталкиваюсь с проблемой, где я ищу специальный тип узла на графике.
Алгоритм работает следующим образом: < /p>

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

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

if(isSpecial)
markCurrentNodeSpecial(n);

return isSpecial;
}
< /code>

Выше выше - это шаблон алгоритма, предполагая, что вход - это Dag.
он ищет специальные узлы на графике и отмечает текущий узел, если какой -либо узел в его дереве DFS является особенным. < /p>

Альгоритм algorithm - это на основе. />
, однако, может привести к переполнению стека в некоторых редких случаях. < /p>

Я пытаюсь выяснить, можно ли сделать то же самое итеративно или нет.>

Подробнее здесь: https://stackoverflow.com/questions/587 ... ursive-dfs