前后数字

Question

当做一个depth first search关于Directed Graph什么意思pre和post数字？

例如:

如果您从节点开始A并按字母顺序Depth First Search执行,那么如何确定前后数字？

Answer 1

注意:虽然这个问题已经问过很久了,但可能会被别人推荐.

Depth First Search中的Pre和Post值分别描述了访问的开始时间和顶点的访问结束时间.从开始时间开始,我指的是发现顶点的时间,结束时间是指将访问所有子节点(在DFS树中)的时间.

这是DFS的示例伪代码 -

dfs(Graph, Vertex)

    static count = 1
    pre[Vertex] = count++
    visited[Vertex] = true

    for all v in Edge(Vertex, v)
        if visited[v] = false
            dfs(Graph, v)

    post[Vertex] = count++;

前后值非常重要.边缘分类就是这样一个例子.此外,您还可以找到使用源值和汇点的帖子值.