Нерекурсивный обход графа после заказа?

Question

Я ищу какой-нибудь псевдокод, алгоритм или руководство, которое поможет мне найти правильный итеративный алгоритм обхода после заказа для обобщенных структур данных графа.

Я нашел много ресурсов (например,два стека или один стек), которые прекрасно работают с деревьями, но не подходят для графов, поскольку они не могут обрабатывать циклы / обратные ребра, поперечные ребра и т. д.

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

template<typename V, typename E>
void tGraph<V, E>::RecursivePostOrderSearch(const tGraph& g, const VertexType& u, std::set<VertexType>& visited, std::vector<VertexType>& result)
{
    if (visited.find(u) == visited.end())
    {
        visited.insert(u);

        EdgeSet edgesOut = g.outgoingEdgesOf(u);

        for(typename EdgeSet::const_iterator iter = edgesOut.begin(); iter != edgesOut.end(); iter++)
        {
            RecursivePostOrderSearch(g, iter->second.second, visited, result);
        }

        result.push_back(u);
    }
}

template<typename V, typename E> std::vector<V> tGraph<V, E>::postOrderList(const VertexType& v) const
{
    std::set<V> visited;
    std::vector<V> result;

    RecursivePostOrderSearch(*this, v, visited, result);

    return result;
}

Где V - тип узла, E - тип ребра - пара «веса» и пары входящих / исходящих узлов.

Если я запускаю ::postOrderList на следующем графике (с корневым узлом A):

Я ожидаю получитьследующие узлы в этом порядке (по краям следуют по порядку их веса):

• D, E, F, B, G, C,A

… И мой рекурсивный алгоритм, приведенный выше, действительно дает правильный results.

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

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

Заранее спасибо.

Answer 1

result.push_back проблематично, но его можно обработать, обработав каждый узел дважды, используя флаг, чтобы указать, хотите ли вы посещать детей или отодвинуть его назад.

Чтобы реализовать это, вы можете использовать стек /вектор со структурой, содержащей "u" и bool (для флага).

Что-то вроде этих строк:

template<typename V, typename E>
void tGraph<V, E>::PostOrderSearch(const tGraph& g, const VertexType& u, std::set<VertexType>& visited, std::vector<VertexType>& result)
{
    std::vector<std::pair<VertexType,bool> > stack;
    stack.push_back(std::pair<VertexType, bool>(u,false));
    for(;;) {
      if (stack.empty()) return; // Done.
      std::pair<VertexType, bool> item=stack.back();
      stack.pop_back();
      VertexType u=item.first;
      if (item.second) {
         // Post-visit
         result.push_back(u);
      }
      else if (visited.find(u)==visited.end()) {
        // Add in reverse order, due to stack
        visited.insert(u);

        EdgeSet edgesOut = g.outgoingEdgesOf(u);

        stack.push_back(std::pair<VertexType, bool>(u,true));   

        for(typename EdgeSet::const_reverse_iterator iter = edgesOut.rbegin(); iter != edgesOut.rend(); iter++)
        {
            stack.push_back(std::pair<VertexType,bool>(iter->second.second,false));
        }
     }
}