图pre-order/post-order遍历？

Question

这是一个DFS前序顶点编号，对应于DFS树的前序遍历，第二个是A post-order numbering，对应于post- DFS树的顺序遍历

谁能解释一下我们是如何得到这个顺序的，因为我只知道如何在二叉树上应用预序或 post-序。谢谢

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 填充它

图pre-order/post-order遍历？

Graph pre-order/post-order traversal?

java

traversal

depth-first-search

data-structures