非递归post阶图遍历?
Non-recursive post-order graph traversal?
我正在寻找一些伪代码、算法或指南,以帮助我为广义图形数据结构找到合适的迭代 post 阶遍历算法。
我发现了很多资源(比如两层或一层算法)非常适合处理树,但无法处理图,因为它们无法处理循环/反向边缘、交叉边缘等。
我已经成功编写了一个递归post阶图遍历算法,它看起来像这样:
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
是边缘类型——一对 "weight" 和传入/传出节点对。
如果我在下图中运行 ::postOrderList
(根节点A
):
我希望按此顺序获得以下节点(边缘按权重顺序排列):
D
, E
, F
, B
, G
, C
, A
…我上面的递归算法确实提供了正确的结果。
但是,尝试将其转换为迭代算法对我来说一直是一个挑战,而且我在这方面没有取得任何成功。我试过转换为尾递归,这样我就可以转换为迭代,但我想不通。我也尝试过转换基于树的双栈和单栈算法,但我也无法在那里正确复制结果。
我已经看到类似的堆栈溢出问题,但 none 似乎涵盖了实际的迭代算法、伪代码或递归到迭代的这种算法的转换,所以我相信任何这方面的指导真的会有帮助。
提前致谢。
result.push_back是有问题的,但可以通过处理每个节点两次来解决,使用一个标志来指定是要访问子节点还是将其推回。
要实现这一点,您可以将 stack/vector 与包含 "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));
}
}
}
我正在寻找一些伪代码、算法或指南,以帮助我为广义图形数据结构找到合适的迭代 post 阶遍历算法。
我发现了很多资源(比如两层或一层算法)非常适合处理树,但无法处理图,因为它们无法处理循环/反向边缘、交叉边缘等。
我已经成功编写了一个递归post阶图遍历算法,它看起来像这样:
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
是边缘类型——一对 "weight" 和传入/传出节点对。
如果我在下图中运行 ::postOrderList
(根节点A
):
我希望按此顺序获得以下节点(边缘按权重顺序排列):
D
,E
,F
,B
,G
,C
,A
…我上面的递归算法确实提供了正确的结果。
但是,尝试将其转换为迭代算法对我来说一直是一个挑战,而且我在这方面没有取得任何成功。我试过转换为尾递归,这样我就可以转换为迭代,但我想不通。我也尝试过转换基于树的双栈和单栈算法,但我也无法在那里正确复制结果。
我已经看到类似的堆栈溢出问题,但 none 似乎涵盖了实际的迭代算法、伪代码或递归到迭代的这种算法的转换,所以我相信任何这方面的指导真的会有帮助。
提前致谢。
result.push_back是有问题的,但可以通过处理每个节点两次来解决,使用一个标志来指定是要访问子节点还是将其推回。
要实现这一点,您可以将 stack/vector 与包含 "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));
}
}
}