Поддержание контекста текущего узла в итеративной DFS против рекурсивной DFS - PullRequest
Новая
       34

Поддержание контекста текущего узла в итеративной DFS против рекурсивной DFS

0 голосов
/ 05 ноября 2019

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

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 является особенным.

Алгоритм в основном заполняет этот специальный атрибут везде, где он доступен.

ЭтоОднако в некоторых редких случаях это может привести к переполнению стека.

Я пытаюсь выяснить, можно ли сделать то же самое итеративно или нет. Проблема итеративного подхода заключается в том, что информация о том, обрабатываются ли все дочерние элементы узла, недоступна.

Любое предложение?

1 Ответ

1 голос
/ 05 ноября 2019

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