Преобразование рекурсивной топологической сортировки на основе 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, может быть, какая-то другая структура данных?
Или, может быть, этот алгоритм в порядке, и я должен оставить его в своей рекурсивной форме (я беспокоюсь только о превышении «глубины рекурсии» для достаточно больших графов)?
Решение
Очевидно, что вы бы использовали стек, но в любом случае не поместили бы все смежные узлы: это все равно привело бы к 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 тривиально.
Другие решения