非递归后序图遍历？

Question

我正在寻找一些伪代码、算法或指南，以帮助我为广义图数据结构找到合适的迭代后序遍历算法。

\n\n

我发现了大量的资源（例如两栈或一栈算法）非常适合树，但对于图来说却很糟糕，因为它们无法处理循环/后边缘、交叉边缘等。

\n\n

我已经成功编写了一个递归后序图遍历算法，如下所示：

\n\n

template<typename V, typename E>\nvoid tGraph<V, E>::RecursivePostOrderSearch(const tGraph& g, const VertexType& u, std::set<VertexType>& visited, std::vector<VertexType>& result)\n{\n    if (visited.find(u) == visited.end())\n    {\n        visited.insert(u);\n\n        EdgeSet edgesOut = g.outgoingEdgesOf(u);\n\n        for(typename EdgeSet::const_iterator iter = edgesOut.begin(); iter != edgesOut.end(); iter++)\n        {\n            RecursivePostOrderSearch(g, iter->second.second, visited, result);\n        }\n\n        result.push_back(u);\n    }\n}\n\ntemplate<typename V, typename E> std::vector<V> tGraph<V, E>::postOrderList(const VertexType& v) const\n{\n    std::set<V> visited;\n    std::vector<V> result;\n\n    RecursivePostOrderSearch(*this, v, visited, result);\n\n    return result;\n}\n

\n\n

其中V是节点类型，E是边类型——“权重”对和传入/传出节点对。

\n\n

如果我在下图上运行::postOrderList（带有根节点A）：

\n\n

\n\n

我希望按此顺序获得以下节点（边按其权重顺序排列）：

\n\n

\n
• D,,,,,,,,E​F​B​G​C​A
\n

\n\n

\xe2\x80\xa6 而我上面的递归算法确实提供了正确的结果。

\n\n

然而，尝试将其转换为迭代算法对我自己来说一直是一个挑战，而且我在这方面没有取得任何成功。我尝试转换为尾递归，这样我就可以转换为迭代，但我无法弄清楚。我还尝试转换基于树的两堆栈和单堆栈算法，但也无法在那里正确复制结果。

\n\n

我见过类似的堆栈溢出问题，但似乎没有一个涵盖实际的迭代算法、伪代码或此类算法的递归到迭代翻译，因此我相信在这个方向上的任何指导都会真正有所帮助。

\n\n

提前致谢。

\n

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