我对该图的后序遍历是否正确？

Question

我正在尝试实现一种需要 post 顺序遍历的算法。这是我的图表（取自 here，第 8 页）：

当我尝试对此进行post顺序遍历时，我得到的顺序是：

[3, 2, 1, 5, 4, 6]

此顺序的问题在于算法无法按此顺序运行。这是我用来获取它的代码（伪代码）：

function PostOrder(root, out_list) {
    root.visited = true
    for child in root.Children {
        if not child.visited {
            PostOrder(child, out_list)
        }
    }
    out_list.append(root)
}

post顺序正确吗？

Answer 1

我想你对二叉树的post顺序遍历感到困惑。

图中的后序遍历不同。

Post Ordering in Graphs – If we list the vertices in the order in which they are last visited by DFS traversal then the ordering is called PostOrder.

假设你的根节点是6，所提到的顺序给出了正确答案。

查看以下示例，了解如何生成 post 订单遍历列表：

第 1 关：

列表：[]

6 -> 5 -> 1 -> 2 -> 3 （现在 Node 3 没有未访问的相邻节点）

列表：[3]

第 2 轮：

6 -> 5 -> 1 -> 2

Node 2没有未访问的相邻节点。

列表：[3, 2]

第 3 关：

6 -> 5 -> 1

Node 1没有未访问的相邻节点。

列表：[3, 2, 1]

第 4 次：

6 -> 5

Node 5没有未访问的相邻节点。

列表：[3、2、1、5]

第 5 次：

6 -> 4

Node 4没有未访问的相邻节点。

列表：[3、2、1、5、4]

第 6 关：

Node 6没有未访问的相邻节点。

列表：[3、2、1、5、4、6]

重要提示：

由于我们使用的是 DFS，因此可能存在多条路径，具体取决于邻接列表中节点的顺序。
可能是正确的顺序：
1. [3, 2, 1, 5, 4, 6]
2. [1, 3, 2, 4, 5, 6]
3. [3、1、2、4、5、6]
4. [1, 2, 3, 4, 5, 6]

Answer 2

是的，你算法的post顺序遍历是正确的。预期输出确实如您提供的那样。

您的困惑可能来自于该图不是二叉树，甚至不是树。这是一个有向图。

一般来说，postorder 意味着你首先在第一个出边后面的节点上执行 postorder 遍历，然后在它的下一个出边后面的节点上，...等等，只有遍历所有出边后，才输出节点本身。

因为在节点 1 你还没有结束，仍然可以去 2，从那里到 3，你需要在输出任何东西之前跟随那些边缘。然后才回溯。

供参考，这是您实现的算法in python：

def postorder(root, out_list, children, visited):
    visited[root] = True
    for child in children[root]:
        if not visited[child]:
            postorder(child, out_list, children, visited)
    out_list.append(root)

children = [
    [],      # dummy for node 0
    [2],     # 1
    [1,3],   # 2
    [2],     # 3
    [2,3],   # 4
    [1],     # 5
    [5,4]    # 6 
]

nodes = []
postorder(6, nodes, children, [False] * len(children))

print(nodes) # [3, 2, 1, 5, 4, 6]

我对该图的后序遍历是否正确？

Is my postorder traversal of this graph correct?

algorithm

graph

tree

traversal

postorder