1

我在这里查看 DFS 伪代码

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;
}

为什么作者在访问所有邻居后将顶点标记为未访问？这是这里必需的步骤吗？既然我们只是在搜索一个顶点，那么如果不将顶点标记为未访问过，它就不能工作吗？

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

4

1 回答 1

4

当您正在寻找顶点而不是顶点本身的路径时，应将顶点标记为未访问。

想象一下，您没有在遍历后将顶点标记为未访问，并且某些搜索会遍历图的一部分并确实找到了指向相关顶点的路径。在某些时候，搜索用尽了可以探索的边缘，并将其步骤回溯到某个较早的点，然后从那里继续。

如果正在搜索的顶点有另一条路径穿过同样位于找到的第一条路径上的顶点，则算法将找不到第二条路径，因为它会将公共顶点视为已经访问过。

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

于 2012-12-12T13:26:45.297 回答