algorithm - 该图伪代码的功能

Question

procedure explore(G; v)
Input: G = (V;E) is a graph; v 2 V
Output: visited(u) is set to true for all nodes u reachable from v


visited(v) = true
previsit(v)
for each edge (v; u) 2 E:
if not visited(u): explore(u)
postvisit(v)

所有这些伪代码所做的就是找到一条路径，对吗？如果我没记错的话，它在回溯时什么都不做？

Answer 1

它只是探索图(它不返回路径)——所有从起始顶点可达的东西都将被探索并在 visited 集合中有相应的值(不仅仅是对应于其中一条路径)。

它在回溯时移动到下一个边...并且它执行postvisit。

因此，如果我们在 a，它有到 b、c 和 d 的边，我们'将从转到 b 开始，然后，当我们最终返回到 a 时，我们将转到 c(如果它没有' t 已经访问过)，然后我们将在第二次返回 a 后类似地转到 d。

它叫做 depth-first search ，以防万一你想知道。维基百科还给出了一个示例，说明在树中探索顶点的顺序:(数字对应于访问顺序，我们从 1 开始)

在上面，你不只是探索左边的顶点(1-4)，而是在 4 之后你回到3访问5，然后回到2访问6，以此类推，直到所有访问了 12 个。

关于 previsit 和 postvisit - previsit 会在我们第一次到达顶点时发生，postvisit在我们探索了所有它的 child (以及它们在相应的 DFS 树中的后代)之后会发生。因此，在上面的示例中，对于 1，previsit 会在开始时发生，但 post-visit 只会在最后发生，因为所有顶点都是子节点1 或这些 child 的后代。订单将是这样的:

pre 1, pre 2, pre 3, pre 4, post 4, pre 5, post 5, post 3, pre 6, post 6, post 2, ...