非递归后序图遍历？

Question

非递归后序图遍历？

5

我希望能够找到一些伪代码、算法或指导，以帮助我为广义图数据结构找到适当的迭代后序遍历算法。

我已经找到了很多资源（如使用两个栈或一个栈的算法），它们在树上运行得很好，但对于图来说就会出现问题，因为它们无法处理循环/反向边、交叉边等。

我已经成功编写了一个递归后序图遍历算法，它看起来像这样：

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

…我的递归算法确实提供了正确的结果。

然而，尝试将其转换为迭代算法一直是困难的，我自己也没有成功。我尝试将其转换为尾递归，以便可以转换为迭代，但我无法弄清楚。我还尝试将基于树的两个堆栈和一个堆栈算法转换，但在那里也无法正确复制结果。

我看到类似的堆栈溢出问题，但没有涵盖实际迭代算法、伪代码或递归到迭代转换的问题，因此任何对该方向的指导都将真正有助于解决问题。

提前感谢。

- tjgrant

相关链接：https://dev59.com/3nM_5IYBdhLWcg3wn0vT - Ciro Santilli OurBigBook.com

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hans Olsson · Accepted Answer

result.push_back的问题在于每个节点都要访问两次，可以通过使用标志来指定是否要访问子节点或将其添加到向量中来处理。

为了实现这一点，您可以使用一个包含“u”和布尔值（用于标志）的结构体的堆栈/向量。

大致如下：

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