Преобразование рекурсивной топологической сортировки на основе DFS в нерекурсивный алгоритм (без потери обнаружения цикла)

Вот псевдокод топологической сортировки из Википедии:

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

Я хочу написать это нерекурсивно, не теряя обнаружения циклов.

Проблема в том, что я не знаю, как это сделать, и я уже придумал много подходов. В основном проблема заключается в том, чтобы сделать DFS, но с запоминанием «текущего пути» (он соответствует «временной маркировке» определенных узлов в псевдокоде выше). Таким образом, традиционный подход со стеком ничего мне не дает, потому что при использовании стека (и размещении в нем соседей каждого узла) я помещаю туда узлы, хотя я увижу их «в неопределенном будущем», и я хочу только отслеживать узлы "на моем текущем пути" (я вижу это как прохождение лабиринта с нитью, которую я оставляю позади себя - когда я вижу тупик, я поворачиваюсь назад и "оборачиваю гусеницу" при этом и в любой момент в время я хочу запомнить узлы "с лежащей на них нитью" и узлы, на которых нить была хотя бы один раз). Любые советы, которые укажут мне в правильном направлении? Я имею в виду - должен ли я думать об использовании 2 стеков вместо 1, может быть, какой-то другой структуры данных?

Или, может быть, этот алгоритм в порядке, и я должен оставить его в рекурсивной форме. Меня беспокоит только превышение «глубины рекурсии» для достаточно больших графов.


c++ recursion graph algorithm topological-sort
person qiubit    schedule 29.12.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Очевидно, вы бы использовали стек, но все равно не поместили бы все соседние узлы: это в любом случае дало бы DFS с неправильной сложностью размера (это было бы квадратично по количеству узлов, предполагающих непараллельные ребра, в противном случае потенциально хуже) . Вместо этого вы должны сохранить текущий узел вместе с состоянием, указывающим следующий посещаемый узел. Вы всегда будете работать с вершиной стека, т.е. что-то вроде этого:

std::stack<std::pair<node, iterator> stack;
stack.push(std::make_pair(root, root.begin()));
while (!stack.empty()) {
    std::pair<node, iterator>& top = stack.top();
    if (top.second == top.first.begin()) {
        mark(top.first);
        // do whatever needs to be done upon first visit
    }
    while (top.second != top.first.end() && is_marked(*top.second)) {
        ++top.second;
    }
    if (top.second != top.first.end()) {
        node next = *top.second;
        ++top.second;
        stack.push(std::make_pair(next, next.first());
    }
    else {
        stack.pop();
    }
}

Этот код предполагает, что узлы имеют begin() и end(), что дает подходящие итераторы для перебора соседних узлов. Что-то в этом духе, возможно, с косвенным обращением через ребра, безусловно, будет существовать. Также предполагается, что существуют функции, доступные для доступа к метке узла. В более реалистичной реализации, которая, вероятно, использовала бы что-то вроде карты свойств BGL. Можно ли использовать std::stack<T> для представления стека, зависит от того, требуется ли доступ к узлам, находящимся в настоящее время в стеке: std::stack не предоставляет такого доступа. Однако создать подходящую реализацию стека на основе любого из контейнеров последовательности STL несложно.

person Dietmar Kühl    schedule 29.12.2014