Post-顺序图遍历？
Post-order Graph Traversal?
给定下面的有向图，我们是如何实现post-order遍历的？
DFS
前序遍历的访问顺序：1 2 5 4 6 3
Post顺序遍历中的访问顺序：4 6 5 2 1 3
Post-order DFS本质上有以下设计：
- 访问 children;
- 拜访自己；
从 1 开始，按以下顺序探索节点：
1 -> 2 -> 5 -> 4(v) -> 6(v) -> 5(v) -> 2(v) -> 1(v) -> 3(v)
此处 (v) 表示在看到其 children 中的 none 未被访问或至少它们在访问管道中后，现在访问该节点。这就解释了为什么遍历是465213.
可能，困扰您的是我们如何访问节点 3，因为从 1 开始没有到 3 的路径。答案似乎是在扫描了整个 connected 图之后，遍历算法会扫描是否还有未扫描的节点。所以最后它最终访问了3。
给定下面的有向图，我们是如何实现post-order遍历的？
DFS
前序遍历的访问顺序：1 2 5 4 6 3
Post顺序遍历中的访问顺序：4 6 5 2 1 3
Post-order DFS本质上有以下设计：
- 访问 children;
- 拜访自己；
从 1 开始，按以下顺序探索节点：
1 -> 2 -> 5 -> 4(v) -> 6(v) -> 5(v) -> 2(v) -> 1(v) -> 3(v)
此处 (v) 表示在看到其 children 中的 none 未被访问或至少它们在访问管道中后，现在访问该节点。这就解释了为什么遍历是465213.
可能，困扰您的是我们如何访问节点 3，因为从 1 开始没有到 3 的路径。答案似乎是在扫描了整个 connected 图之后，遍历算法会扫描是否还有未扫描的节点。所以最后它最终访问了3。