后序图遍历？

Question

鉴于下面的有向图,我们如何实现后序遍历？

DFS

预订遍历中的访问顺序:1 2 5 4 6 3

在订购后遍历中的访问订单:4 6 5 2 1 3

Answer 1

订购后的DFS基本上有以下设计:

1. 拜访孩子们;
2. 拜访自己;

从开始1,按以下顺序探索节点:

1- > 2- > 5- > 4(v)- > 6(v)- > 5(v)- > 2(v)- > 1(v)- >3(v)

这(v)意味着在看到节点没有任何子节点未被访问或者至少它们在管道中进行访问之后,现在访问该节点.这解释了遍历的原因465213.

可能困扰你的是我们如何访问节点,3因为从1没有路径开始3.答案似乎是在扫描完整个连接图之后,遍历算法会扫描是否还有未扫描的节点.所以最后它最终会访问3.