algorithm - 深度优先搜索递归算法

Question

我正在查看 DFS 伪代码 here

dfs(node start) {
 stack s;
 s.push(start);
 while (s.empty() == false) {
  top = s.top();
  s.pop();
  mark top as visited;

  check for termination condition

  add all of top's unvisited neighbors to the stack.
  mark top as not visited;
 }
}

dfs(node current) {
 mark current as visited;
 visit all of current's unvisited neighbors by calling dfs(neighbor)
 mark current as not visited;
}

为什么作者在访问了所有邻居之后将一个顶点标记为未访问过？这是这里必需的步骤吗？由于我们只是在搜索一个顶点，如果不将该顶点标记为未访问过，它是否会起作用？

另一个链接 here在将顶点设置为已访问后，实际上并没有将其标记为未访问。

Answer 1

当您寻找一个顶点的路径而不是顶点本身时，该顶点应该被标记为未访问。

假设您在遍历后没有将顶点标记为未访问过，并且某些搜索遍历了图的一部分并确实找到了到相关顶点的路径。在某个点，搜索用完了边缘以进行探索，并将其步骤回溯到某个较早的点，然后从那里继续。

如果另一路径指向正在搜索的顶点，该路径穿过也在找到的第一条路径上的顶点，则该算法将找不到第二条路径因为它会将公共(public)顶点视为已经访问过。

另一方面，如果您只寻找一条路径(或只寻找一个顶点的存在，即根本没有路径)，那么您可以跳过将节点标记为“在离开时”未访问过的步骤。