图的前序/后序遍历？

Question

这是一种深度优先搜索（DFS）的前序顶点编号，它对应于DFS树的前序遍历，第二种是一种后序编号，它对应于DFS树的后序遍历。

有人能否解释一下我们如何得到这个顺序，因为我只知道如何在二叉树上应用前序或后序。谢谢。

- Square-root

---

你知道深度优先搜索是如何工作的吗？如果使用先序遍历，首先选择根节点，例如在你的例子中选择权重最小的1，然后搜索并选择另一个节点，其权重小于除父节点外所有其他节点，并且不会形成环路，重复步骤2直到覆盖所有顶点。 - CY5

DFS 在任何图形上的工作方式与（二叉）树类似 - 主要区别在于算法必须显式地防止循环图中的循环（这在树中不会发生）。如果节点值遵循某些定义的规则，则可以隐式解决此问题。 - user2864740

Answer 1

尝试按照伪代码的步骤和你的示例一步步跟踪，你就能理解这个算法了，它非常容易，只是纯粹的DFS：

Initialize clock to 1

PreVisit(v):
    pre[v] <- clock
    clock <- clock + 1

PostVisit(v):
    post[v] <- clock
    clock <- clock + 1

Explore(v):
    visited[v] = true
    PreVisit(v)
    for all u adj to v:
        if u is not visited:
            Explore(u)
    PostVisit(v)

请注意，您需要创建一个长度为顶点数的pre、post和visited数组。对于visited数组，您需要在调用Explore(v)之前将其填充为false。

- Huy Vo

---

你还应该为前序和后序遍历定义不同的时钟。 - Nearoo