为什么 DFS 不检查选择用于开发的节点的 children 的目标状态

Question

抱歉，如果我的语法还不够完美，英语不是我的母语。

如果我理解正确，DFS 仅在选择节点进行开发时才对节点进行目标测试，而不是在生成节点时。这对我来说似乎很奇怪，因为在 DFS 选择一个节点进行开发之后，它无论如何都会将该节点的所有 children 添加到打开列表中。在这样做的同时，为什么不检查它的一个 children 是否是目标状态，如果是这样，DFS 可以 return 解决方案并终止？生成目标状态后继续在更深层次上搜索似乎是在浪费大量时间，我错了吗？

非常感谢！

Answer 1

不，你没看错，当然如果你在当前节点的neighbors（你的说法是children）中找到了目的地，你就可以终止它。

但是，由于两个原因，我会坚持"standard"实施：（只是我个人的顾虑）

实现更简单，可读性更高，比如你可能想在到达目的地后做一些事情，那么标准的方式和你的方式，伪代码是这样的

//The way I like to implement
void dfs(int x){
  if(x is destination){
     do_something(); return;
  }
  mark x visited
  foreach x's unvisited neighbor{
      dfs(x's neighbor)
  }
}
          
//The way you suggest to implement
void dfs(int x){
  mark x visited
  foreach x's unvisited neighbor{
      if(x's neighbor is destination){
         do_something(); return;
      }
      dfs(x's neighbor)
  }
}

我只是认为，由于 DFS 是基于递归的，并且根据我的理解，将基本情况检查从 FOR 循环中移出，将其放在函数的第一位是更 "recursion-like" 的实现.

此外，如果 do_something() 是一项相当复杂的任务，如果将检查和处理放在 For 循环中（可读性问题），代码可能会变得混乱

时间复杂度相同你是对的，它可以节省很多递归层次，取决于节点横向的顺序。

但是，为了节省时间而放弃上面提到的可读性是否值得呢？我不这么认为。

由于时间复杂度相同，只要每个节点最多访问一次，复杂度为O(N+M)，其中N是节点数，M是边数

所以不值得冒险写一些乱七八糟的代码来节省一般来说可以忽略不计的时间

为什么 DFS 不检查选择用于开发的节点的 children 的目标状态

Why DFS doesn't check children of a node, that was chosen for development, for a goal state

algorithm

time

search

time-complexity

depth-first-search