如果你的结果是在 BFS 图中但不是 DFS 图中，为什么你能保证找到结果呢？
我在某处读到，DFS 不能保证找到解决方案，而 BFS 可以......为什么？我真的不明白这是怎么回事。有人可以为我演示一个案例来证明这一点吗？
I've read somewhere that DFS is not gaurenteed to find a solution while BFS is.. why? I don't really get how this is true.. could someone demonstrate a case for me that proves this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
DFS，由于它是深度优先搜索，可能会陷入无限分支，永远无法到达您正在寻找的顶点。 BFS 每次迭代都会遍历距根相同距离的所有顶点，无论它们位于哪个分支，因此最终会找到所需的顶点。
示例：
根-> v1-> v2-> v3-> ...永远持续下去
|-> u。
在此示例中，如果 DFS 从根开始，然后继续到 v1。它永远不会到达你，因为它进入的分支是无限的。 BFS 将从 root 转到 v1 或 u，然后再转到另一个。
DFS, since its a Depth first search, could get stuck in an infinite branch and never reach the vertex you're looking for. BFS goes through all vertices at the same distance from the root each iteration, no matter what branch they're on so it will find the desired vertex eventually.
example:
root -> v1 -> v2 -> v3 -> ... goes on forever
|-> u.
in this example, if DFS begins at the root and then goes on to v1. it will never reach u since the branch it entered is infinite. BFS will go from root to either v1 or u and then to the other.
DFS 和 BFS 的输出（在具有有限数量顶点的图上）终止并产生一条路径（或者更确切地说是一棵树，但 OP 似乎只对该树的一条路径感兴趣）。图中是否存在环并不重要，因为这两个过程都会记录哪些顶点已经被访问过，从而避免多次访问同一顶点。任何健全的 DFS/BFS 实现都会执行此操作 - 否则您将仅限于非循环图（请参阅 CLRS 中给出的伪代码）。
正如 @yurib 提到的，如果图有无限数量的节点，dfs 可能会花费很长时间。由于存在无限节点，我们实际上无法跟踪哪些顶点已经被访问过（这可能会占用无限的内存），即使我们这样做了，也可能存在一条包含唯一顶点的无限路径，但该路径不包含我们正在寻找的顶点。
然而，这并不是 DFS 并不总是找到最短路径的唯一原因。即使在有限图中，DFS 也可能无法找到最短路径。
主要原因是 BFS 总是先探索距根部距离为 x 的所有节点，然后再继续探索距根部距离为 x+1 的节点。因此，如果在距离 k 处找到一个节点，我们可以确定从根到该节点的最小距离是 k，而不是 k-1, k-2,...,0（否则我们会更早遇到它）。
另一方面，DFS 基本上沿着一条路径探索节点，直到该路径上不再有新节点，然后再查看另一条路径。 DFS 只是以基本上任意的顺序逐一探索节点的每个后继节点。这意味着它可能会找到一条通往目标节点的更长路径，因为它恰好首先探索了该路径。
在上图中，BFS 将首先探索 B 和 E，然后通过 E 到达 D - 给我们到 D 的路径作为 root->E->D。 DFS可能会先从B开始搜索，从而找到路径root->B->C->D，这显然不是最短的。
请注意，关键的决定是在 E 之前探索 B。DFS 很可能选择 E 并得出正确答案。但通常没有办法知道先走哪条路径（如果我们知道无论如何我们都会知道最短路径）。对于 DFS，它找到的路径仅取决于它探索后继节点的顺序，这可能会也可能不会产生最短路径。
The output of both DFS and BFS (on graphs with a finite number of vertices) terminate and yield a path (or rather a tree, but the OP only seems to be interested in one path of that tree). It does not matter whether there are cycles in the graph, because both procedures keep a record of which vertices have already been visited and thus avoids visiting the same vertex more than once. Any sane implementation of DFS/BFS does this - otherwise you'd be constrained to acyclic graphs only (see the pseudocode given in CLRS).
As @yurib mentioned, if the graph has an infinite number of nodes, dfs can take forever. Since there are infinite nodes, we cannot practically keep track of which vertices were already visited (that would take potentially infinite memory) and even if we did, there maybe be an infinite path containing unique vertices which does not contain the vertex we are looking for.
However, that is not the only reason DFS does not always find the shortest path. Even in finite graphs, DFS may fail to find the shortest path.
The main reason is that BFS always explores all nodes at distance x from the root before moving on to those at distance x+1. Thus if a node is found at distance k, we can be sure the minimum distance from the root to that node is k and not k-1, k-2,...,0 (otherwise we would have encountered it earlier).
DFS, on the other hand, basically explores nodes along one path until there are no more new nodes down that path before looking at a different path. DFS just explores each successor of a node one by one, in an essentially arbitrary order. This means it may find a longer path to the target node just because it just happened to explore that path first.
In the image above, a BFS would explore B and E first, and then reach D via E - giving us the path to D as root->E->D. A DFS might start search from B first, thus finding the path root->B->C->D, which is clearly not the shortest.
Notice the crucial decision was to go for exploring B before E. A DFS might well have chosen E and arrived at the correct answer. But there is in general no way to know which path to go down first (if we knew that we would know the shortest path anyway). For a DFS the path which it finds simply depends on the order in which it explores the successor nodes, which may or may not yield a shortest path.