gpt4 book ai didi

depth-first-search - 前后编号

转载 作者:行者123 更新时间:2023-12-04 07:53:38 27 4
gpt4 key购买 nike

当做 depth first searchDirected Graph pre 是什么意思和 post数字?

例如:

enter image description here

如果您从节点 A 开始并按字母顺序排列 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++;

前值和后值有很多意义。边缘分类就是这样一个例子。此外,您还可以在源和汇出现的地方找到帖子值的使用。

关于depth-first-search - 前后编号,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21669584/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com