That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items).
If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.
If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.
If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.
If solutions are frequent but located deep in the tree, BFS could be impractical.
If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).
But these are just rules of thumb; you'll probably need to experiment.
I think in practice you'll usually not use these algorithms in their pure form anyway. There could be heuristics that help to explore promising parts of the search space first, or you might want to modify your search algorithm to be able to parallelize it efficiently.
Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.
For example in games like Chess, tic-tac-toe when you are deciding what move to make, you can mentally imagine a move, then your opponent’s possible responses, then your responses, and so on. You can decide what to do by seeing which move leads to the best outcome.
Only some paths in a game tree lead to your win. Some lead to a win by your opponent, when you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Then you make the first move along this path.
Breadth-first search
The breadth-first search has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. You start a BFS, and when you find the specified vertex, you know the path you’ve traced so far is the shortest path to the node. If there were a shorter path, the BFS would have found it already.
Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance and things like that.
Here’s an example of what a BFS would look like. This is something like Level Order Tree Traversal where we will use QUEUE with ITERATIVE approach (Mostly RECURSION will end up with DFS). The numbers represent the order in which the nodes are accessed in a BFS:
In a depth first search, you start at the root, and follow one of the branches of the tree as far as possible until either the node you are looking for is found or you hit a leaf node ( a node with no children). If you hit a leaf node, then you continue the search at the nearest ancestor with unexplored children.
An example of DFS
Here’s an example of what a DFS would look like. I think post order traversal in binary tree will start work from the Leaf level first. The numbers represent the order in which the nodes are accessed in a DFS:
Differences between DFS and BFS
Comparing BFS and DFS, the big advantage of DFS is that it has much lower memory requirements than BFS, because it’s not necessary to store all of the child pointers at each level. Depending on the data and what you are looking for, either DFS or BFS could be advantageous.
For example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS. So, the advantages of either vary depending on the data and what you’re looking for.
One more example is Facebook; Suggestion on Friends of Friends. We need immediate friends for suggestion where we can use BFS. May be finding the shortest path or detecting the cycle (using recursion) we can use DFS.
Breadth First Search is generally the best approach when the depth of the tree can vary, and you only need to search part of the tree for a solution. For example, finding the shortest path from a starting value to a final value is a good place to use BFS.
Depth First Search is commonly used when you need to search the entire tree. It's easier to implement (using recursion) than BFS, and requires less state: While BFS requires you store the entire 'frontier', DFS only requires you store the list of parent nodes of the current element.
DFS is more space-efficient than BFS, but may go to unnecessary depths.
Their names are revealing: if there's a big breadth (i.e. big branching factor), but very limited depth (e.g. limited number of "moves"), then DFS can be more preferrable to BFS.
On IDDFS
It should be mentioned that there's a less-known variant that combines the space efficiency of DFS, but (cummulatively) the level-order visitation of BFS, is the iterative deepening depth-first search. This algorithm revisits some nodes, but it only contributes a constant factor of asymptotic difference.
def dfs(origin): # DFS from origin:
origin.visited = True # Mark the origin as visited
for neighbor in origin.neighbors: # Loop over the neighbors
if not neighbor.visited: dfs(neighbor) # Visit each neighbor if not already visited
如果将“已访问”信息存储在单独的数据结构中： 将
def dfs(node, visited): # DFS from origin, with already-visited set:
visited.add(node) # Mark the origin as visited
for neighbor in node.neighbors: # Loop over the neighbors
if not neighbor in visited: # If the neighbor hasn't been visited yet,
dfs(neighbor, visited) # then visit the neighbor
dfs(origin, set())
其与需要维护的广度优先搜索进行对比无论如何，尚未访问的节点列表的单独数据结构。
When you approach this question as a programmer, one factor stands out: if you're using recursion, then depth-first search is simpler to implement, because you don't need to maintain an additional data structure containing the nodes yet to explore.
Here's depth-first search for a non-oriented graph if you're storing “already visited” information in the nodes:
def dfs(origin): # DFS from origin:
origin.visited = True # Mark the origin as visited
for neighbor in origin.neighbors: # Loop over the neighbors
if not neighbor.visited: dfs(neighbor) # Visit each neighbor if not already visited
If storing “already visited” information in a separate data structure:
def dfs(node, visited): # DFS from origin, with already-visited set:
visited.add(node) # Mark the origin as visited
for neighbor in node.neighbors: # Loop over the neighbors
if not neighbor in visited: # If the neighbor hasn't been visited yet,
dfs(neighbor, visited) # then visit the neighbor
dfs(origin, set())
Contrast this with breadth-first search where you need to maintain a separate data structure for the list of nodes yet to visit, no matter what.
One important advantage of BFS would be that it can be used to find the shortest path between any two nodes in an unweighted graph. Whereas, we cannot use DFS for the same.
深度优先搜索（DFS）算法，顾名思义就是“深度”，通过其出边来发现最近发现的节点 x 的未访问邻居。如果节点 x 没有未访问的邻居，则算法回溯以发现发现节点 x 的节点的未访问邻居（通过其出边），依此类推，直到访问了从原始源可达的所有节点。 （如果还有剩余的未访问节点等，我们可以继续并获取另一个原始源）。
The following is a comprehensive answer to what you are asking.
In simple terms:
Breadth First Search (BFS) algorithm, from its name "Breadth", discovers all the neighbours of a node through the out edges of the node then it discovers the unvisited neighbours of the previously mentioned neighbours through their out edges and so forth, till all the nodes reachable from the origional source are visited (we can continue and take another origional source if there are remaining unvisited nodes and so forth). That's why it can be used to find the shortest path (if there is any) from a node (origional source) to another node if the weights of the edges are uniform.
Depth First Search (DFS) algorithm, from its name "Depth", discovers the unvisited neighbours of the most recently discovered node x through its out edges. If there is no unvisited neighbour from the node x, the algorithm backtracks to discover the unvisited neighbours of the node (through its out edges) from which node x was discovered, and so forth, till all the nodes reachable from the origional source are visited (we can continue and take another origional source if there are remaining unvisited nodes and so forth).
Both BFS and DFS can be incomplete. For example if the branching factor of a node is infinite, or very big for the resources (memory) to support (e.g. when storing the nodes to be discovered next), then BFS is not complete even though the searched key can be at a distance of few edges from the origional source. This infinite branching factor can be because of infinite choices (neighbouring nodes) from a given node to discover. If the depth is infinite, or very big for the resources (memory) to support (e.g. when storing the nodes to be discovered next), then DFS is not complete even though the searched key can be the third neighbor of the origional source. This infinite depth can be because of a situation where there is, for every node the algorithm discovers, at least a new choice (neighbouring node) that is unvisited before.
Therefore, we can conclude when to use the BFS and DFS. Suppose we are dealing with a manageable limited branching factor and a manageable limited depth. If the searched node is shallow i.e. reachable after some edges from the origional source, then it is better to use BFS. On the other hand, if the searched node is deep i.e. reachable after a lot of edges from the origional source, then it is better to use DFS.
For example, in a social network if we want to search for people who have similar interests of a specific person, we can apply BFS from this person as an origional source, because mostly these people will be his direct friends or friends of friends i.e. one or two edges far. On the other hand, if we want to search for people who have completely different interests of a specific person, we can apply DFS from this person as an origional source, because mostly these people will be very far from him i.e. friend of friend of friend.... i.e. too many edges far.
Applications of BFS and DFS can vary also because of the mechanism of searching in each one. For example, we can use either BFS (assuming the branching factor is manageable) or DFS (assuming the depth is manageable) when we just want to check the reachability from one node to another having no information where that node can be. Also both of them can solve same tasks like topological sorting of a graph (if it has). BFS can be used to find the shortest path, with unit weight edges, from a node (origional source) to another. Whereas, DFS can be used to exhaust all the choices because of its nature of going in depth, like discovering the longest path between two nodes in an acyclic graph. Also DFS, can be used for cycle detection in a graph.
In the end if we have infinite depth and infinite branching factor, we can use Iterative Deepening Search (IDS).
Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.
For BFS, we can consider Facebook example. We receive suggestion to add friends from the FB profile from other other friends profile. Suppose A->B, while B->E and B->F, so A will get suggestion for E And F. They must be using BFS to read till second level. DFS is more based on scenarios where we want to forecast something based on data we have from source to destination. As mentioned already about chess or sudoku. Once thing I have different here is, I believe DFS should be used for shortest path because DFS will cover the whole path first then we can decide the best. But as BFS will use greedy's approach so might be it looks like its the shortest path, but the final result might differ. Let me know whether my understanding is wrong.
According to the properties of DFS and BFS. For example,when we want to find the shortest path. we usually use bfs,it can guarantee the 'shortest'. but dfs only can guarantee that we can come from this point can achieve that point ,can not guarantee the 'shortest'.
Because Depth-First Searches use a stack as the nodes are processed, backtracking is provided with DFS. Because Breadth-First Searches use a queue, not a stack, to keep track of what nodes are processed, backtracking is not provided with BFS.
When tree width is very large and depth is low use DFS as recursion stack will not overflow.Use BFS when width is low and depth is very large to traverse the tree.
When correctly implemented, both solutions should visit cells that have farther distance than the current cell +1. But DFS is inefficient and repeatedly visited the same cell resulting O(n*n) complexity.
发布评论
评论（15）
这在很大程度上取决于搜索树的结构以及解决方案（也称为搜索项）的数量和位置。
如果您知道解离树根不远，则
广度优先搜索（BFS）可能会更好。
如果树很深并且解决方案很少，则深度优先搜索
（DFS）可能需要很长的时间，但 BFS 可能会更快。
如果树很宽，BFS可能需要太多内存，所以它
可能完全不切实际。
如果解很频繁但位于树的深处，BFS 可能是
不切实际。
如果搜索树非常深，您将需要限制搜索
无论如何，深度优先搜索（DFS）的深度（例如
迭代深化）。
但这些只是经验法则；你可能需要尝试一下。
我认为在实践中你通常不会以纯粹的形式使用这些算法。可能有一些启发式方法有助于首先探索搜索空间中有前途的部分，或者您可能希望修改搜索算法以使其能够有效地并行化。
That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items).
If you know a solution is not far from the root of the tree, a
breadth first search (BFS) might be better.
If the tree is very deep and solutions are rare, depth first search
(DFS) might take an extremely long time, but BFS could be faster.
If the tree is very wide, a BFS might need too much memory, so it
might be completely impractical.
If solutions are frequent but located deep in the tree, BFS could be
impractical.
If the search tree is very deep you will need to restrict the search
depth for depth first search (DFS), anyway (for example with
iterative deepening).
But these are just rules of thumb; you'll probably need to experiment.
I think in practice you'll usually not use these algorithms in their pure form anyway. There could be heuristics that help to explore promising parts of the search space first, or you might want to modify your search algorithm to be able to parallelize it efficiently.
深度优先搜索
深度优先搜索通常用于游戏模拟（以及现实世界中类似游戏的情况）。在典型的游戏中，您可以选择几种可能的动作之一。每个选择都会导致进一步的选择，每个选择都会导致进一步的选择，依此类推，形成一个不断扩展的树形可能性图。
例如，在国际象棋、井字棋等游戏中，当您决定采取什么行动时，您可以在心里想象一个行动，然后是对手可能的反应，然后是您的反应，等等。您可以通过查看哪种举动会带来最佳结果来决定做什么。
游戏树中只有某些路径会导致您获胜。有些会导致对手获胜，当你达到这样的结局时，你必须后退或回溯到前一个节点并尝试不同的路径。通过这种方式，你可以探索这棵树，直到找到一条成功结束的路径。然后你就沿着这条路迈出了第一步。
广度优先搜索
广度优先搜索有一个有趣的属性：它首先查找距起点一条边的所有顶点，然后查找距起点两条边的所有顶点，依此类推。如果您试图找到从起始顶点到给定顶点的最短路径，这非常有用。你启动一个 BFS，当你找到指定的顶点时，你就知道到目前为止你所追踪的路径是到该节点的最短路径。如果有更短的路径，BFS 早就找到了。
广度优先搜索可用于查找点对点网络（如 BitTorrent）中的邻居节点、用于查找附近位置的 GPS 系统、用于查找指定距离内的人的社交网站等。
Depth-first Search
Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.
For example in games like Chess, tic-tac-toe when you are deciding what move to make, you can mentally imagine a move, then your opponent’s possible responses, then your responses, and so on. You can decide what to do by seeing which move leads to the best outcome.
Only some paths in a game tree lead to your win. Some lead to a win by your opponent, when you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Then you make the first move along this path.
Breadth-first search
The breadth-first search has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. You start a BFS, and when you find the specified vertex, you know the path you’ve traced so far is the shortest path to the node. If there were a shorter path, the BFS would have found it already.
Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance and things like that.
很好的解释来自
http://www.programmerinterview.com/index.php/data-structs/dfs -vs-bfs/
下面是 BFS 的示例。这类似于级别顺序树遍历，我们将使用带有迭代方法的队列（大多数递归将以 DFS 结束）。这些数字表示 BFS 中访问节点的顺序：
在深度优先搜索中，您可以从根开始，尽可能地沿着树的一个分支，直到找到您要查找的节点或找到叶节点（没有子节点的节点）。如果您命中叶节点，则继续在最近的祖先处以及未探索的子节点处进行搜索。
下面是 DFS 的示例。我认为二叉树中的后序遍历将首先从叶级别开始工作。这些数字表示在 DFS 中访问节点的顺序：
比较 BFS 和 DFS，DFS 的一大优点是它的内存需求比 BFS 低得多，因为不需要存储每一级的所有子指针。根据数据和您要查找的内容，DFS 或 BFS 可能更有利。
例如，给定一棵家谱，如果有人在树上寻找还活着的人，那么可以安全地假设该人将在树的底部。这意味着 BFS 需要很长时间才能达到最后一个水平。然而，DFS 会更快地找到目标。但是，如果要寻找一位很久以前去世的家庭成员，那么那个人就会更接近树顶。那么，BFS 通常会比 DFS 更快。因此，两者的优点取决于数据和您正在寻找的内容。
另一个例子是 Facebook；朋友之友的建议。我们需要立即得到朋友的建议，我们可以在哪里使用 BFS。可能是寻找最短路径或检测循环（使用递归），我们可以使用 DFS。
Nice Explanation from
http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/
Here’s an example of what a BFS would look like. This is something like Level Order Tree Traversal where we will use QUEUE with ITERATIVE approach (Mostly RECURSION will end up with DFS). The numbers represent the order in which the nodes are accessed in a BFS:
In a depth first search, you start at the root, and follow one of the branches of the tree as far as possible until either the node you are looking for is found or you hit a leaf node ( a node with no children). If you hit a leaf node, then you continue the search at the nearest ancestor with unexplored children.
Here’s an example of what a DFS would look like. I think post order traversal in binary tree will start work from the Leaf level first. The numbers represent the order in which the nodes are accessed in a DFS:
Comparing BFS and DFS, the big advantage of DFS is that it has much lower memory requirements than BFS, because it’s not necessary to store all of the child pointers at each level. Depending on the data and what you are looking for, either DFS or BFS could be advantageous.
For example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS. So, the advantages of either vary depending on the data and what you’re looking for.
One more example is Facebook; Suggestion on Friends of Friends. We need immediate friends for suggestion where we can use BFS. May be finding the shortest path or detecting the cycle (using recursion) we can use DFS.
当树的深度可能变化时，广度优先搜索通常是最好的方法，并且您只需搜索树的一部分即可找到解决方案。例如，寻找从起始值到最终值的最短路径就是使用 BFS 的好地方。
当需要搜索整个树时，通常使用深度优先搜索。它比 BFS 更容易实现（使用递归），并且需要更少的状态：虽然 BFS 要求您存储整个“边界”，但 DFS 只要求您存储当前元素的父节点列表。
Breadth First Search is generally the best approach when the depth of the tree can vary, and you only need to search part of the tree for a solution. For example, finding the shortest path from a starting value to a final value is a good place to use BFS.
Depth First Search is commonly used when you need to search the entire tree. It's easier to implement (using recursion) than BFS, and requires less state: While BFS requires you store the entire 'frontier', DFS only requires you store the list of parent nodes of the current element.
DFS 比 BFS 更节省空间，但可能会达到不必要的深度。
它们的名字很能说明问题：如果宽度很大（即大分支因子），但深度非常有限（例如“移动”数量有限），那么 DFS 可能比 BFS 更可取。
关于 IDDFS
应该提到的是，有一个不太为人所知的变体，它结合了 DFS 的空间效率，但（累积）BFS 的层序访问，是 迭代加深深度优先搜索。该算法重新访问了一些节点，但它只贡献了渐近差异的常数因子。
DFS is more space-efficient than BFS, but may go to unnecessary depths.
Their names are revealing: if there's a big breadth (i.e. big branching factor), but very limited depth (e.g. limited number of "moves"), then DFS can be more preferrable to BFS.
On IDDFS
It should be mentioned that there's a less-known variant that combines the space efficiency of DFS, but (cummulatively) the level-order visitation of BFS, is the iterative deepening depth-first search. This algorithm revisits some nodes, but it only contributes a constant factor of asymptotic difference.
当您作为程序员解决这个问题时，有一个因素很突出：如果您使用递归，那么深度优先搜索的实现更简单，因为您不需要维护额外的数据结构包含尚未探索的节点。
如果您在节点中存储“已访问”信息，则以下是对无向图的深度优先搜索：
如果将“已访问”信息存储在单独的数据结构中： 将
其与需要维护的广度优先搜索进行对比无论如何，尚未访问的节点列表的单独数据结构。
When you approach this question as a programmer, one factor stands out: if you're using recursion, then depth-first search is simpler to implement, because you don't need to maintain an additional data structure containing the nodes yet to explore.
Here's depth-first search for a non-oriented graph if you're storing “already visited” information in the nodes:
If storing “already visited” information in a separate data structure:
Contrast this with breadth-first search where you need to maintain a separate data structure for the list of nodes yet to visit, no matter what.
BFS 的一个重要优点是它可以用于查找未加权图中任意两个节点之间的最短路径。
然而，我们不能使用 DFS对于相同的。
One important advantage of BFS would be that it can be used to find the shortest path between any two nodes in an unweighted graph.
Whereas, we cannot use DFS for the same.
以下是对您所问问题的全面回答。
简单来说：
广度优先搜索（BFS）算法，顾名思义就是“广度”，通过节点的出边发现节点的所有邻居。该节点然后通过其出边等发现前面提到的邻居的未访问邻居，直到访问了从原始源可达的所有节点（如果还有剩余的未访问节点，我们可以继续并采用另一个原始源，依此类推） ）。这就是为什么如果边的权重是均匀的，它可以用来找到从一个节点（原始源）到另一个节点的最短路径（如果有的话）。
深度优先搜索（DFS）算法，顾名思义就是“深度”，通过其出边来发现最近发现的节点 x 的未访问邻居。如果节点 x 没有未访问的邻居，则算法回溯以发现发现节点 x 的节点的未访问邻居（通过其出边），依此类推，直到访问了从原始源可达的所有节点。 （如果还有剩余的未访问节点等，我们可以继续并获取另一个原始源）。
BFS 和 DFS 都可能是不完备的。例如，如果节点的分支因子是无限的，或者对于要支持的资源（内存）来说非常大（例如，当存储接下来要发现的节点时），那么即使搜索到的键可能在很远的地方，BFS也不完整原始来源的一些边缘。这种无限分支因素可能是因为从给定节点发现的无限选择（相邻节点）。
如果深度是无限的，或者对于要支持的资源（内存）来说非常大（例如，当存储接下来要发现的节点时），则即使搜索到的关键字可以是原始源的第三个邻居，DFS也不完整。这种无限深度可能是因为对于算法发现的每个节点，至少存在一个以前未访问过的新选择（相邻节点）。
因此，我们可以得出何时使用BFS和DFS。假设我们正在处理一个可管理的有限分支因子和一个可管理的有限深度。如果搜索的节点很浅，即在原始源的一些边之后可达，那么最好使用 BFS。另一方面，如果搜索的节点很深，即在来自原始源的许多边之后可达，那么最好使用 DFS。
例如，在社交网络中，如果我们想要搜索与特定人有相似兴趣的人，我们可以应用此人的 BFS 作为原始来源，因为这些人大多是他的直接朋友或朋友的朋友，即一个人或两个边缘远。
另一方面，如果我们想搜索与某个特定人有完全不同兴趣的人，我们可以从这个人作为原始来源应用DFS，因为大多数这些人会离他很远，即朋友的朋友的朋友。 ....即边缘太多。
BFS 和 DFS 的应用也可能因各自的搜索机制而有所不同。例如，当我们只想检查从一个节点到另一个节点的可达性而没有该节点所在位置的信息时，我们可以使用 BFS（假设分支因子是可管理的）或 DFS（假设深度是可管理的）。此外，它们都可以解决相同的任务，例如图的拓扑排序（如果有）。
BFS 可用于查找从一个节点（原始源）到另一个节点的具有单位权重边的最短路径。而 DFS 可以用来穷尽所有选择，因为它具有深入的性质，就像发现非循环图中两个节点之间的最长路径一样。 DFS 也可用于图中的循环检测。
最后，如果我们有无限的深度和无限的分支因子，我们可以使用迭代加深搜索（IDS）。
The following is a comprehensive answer to what you are asking.
In simple terms:
Breadth First Search (BFS) algorithm, from its name "Breadth", discovers all the neighbours of a node through the out edges of the node then it discovers the unvisited neighbours of the previously mentioned neighbours through their out edges and so forth, till all the nodes reachable from the origional source are visited (we can continue and take another origional source if there are remaining unvisited nodes and so forth). That's why it can be used to find the shortest path (if there is any) from a node (origional source) to another node if the weights of the edges are uniform.
Depth First Search (DFS) algorithm, from its name "Depth", discovers the unvisited neighbours of the most recently discovered node x through its out edges. If there is no unvisited neighbour from the node x, the algorithm backtracks to discover the unvisited neighbours of the node (through its out edges) from which node x was discovered, and so forth, till all the nodes reachable from the origional source are visited (we can continue and take another origional source if there are remaining unvisited nodes and so forth).
Both BFS and DFS can be incomplete. For example if the branching factor of a node is infinite, or very big for the resources (memory) to support (e.g. when storing the nodes to be discovered next), then BFS is not complete even though the searched key can be at a distance of few edges from the origional source. This infinite branching factor can be because of infinite choices (neighbouring nodes) from a given node to discover.
If the depth is infinite, or very big for the resources (memory) to support (e.g. when storing the nodes to be discovered next), then DFS is not complete even though the searched key can be the third neighbor of the origional source. This infinite depth can be because of a situation where there is, for every node the algorithm discovers, at least a new choice (neighbouring node) that is unvisited before.
Therefore, we can conclude when to use the BFS and DFS. Suppose we are dealing with a manageable limited branching factor and a manageable limited depth. If the searched node is shallow i.e. reachable after some edges from the origional source, then it is better to use BFS. On the other hand, if the searched node is deep i.e. reachable after a lot of edges from the origional source, then it is better to use DFS.
For example, in a social network if we want to search for people who have similar interests of a specific person, we can apply BFS from this person as an origional source, because mostly these people will be his direct friends or friends of friends i.e. one or two edges far.
On the other hand, if we want to search for people who have completely different interests of a specific person, we can apply DFS from this person as an origional source, because mostly these people will be very far from him i.e. friend of friend of friend.... i.e. too many edges far.
Applications of BFS and DFS can vary also because of the mechanism of searching in each one. For example, we can use either BFS (assuming the branching factor is manageable) or DFS (assuming the depth is manageable) when we just want to check the reachability from one node to another having no information where that node can be. Also both of them can solve same tasks like topological sorting of a graph (if it has).
BFS can be used to find the shortest path, with unit weight edges, from a node (origional source) to another. Whereas, DFS can be used to exhaust all the choices because of its nature of going in depth, like discovering the longest path between two nodes in an acyclic graph. Also DFS, can be used for cycle detection in a graph.
In the end if we have infinite depth and infinite branching factor, we can use Iterative Deepening Search (IDS).
我认为这取决于你面临什么问题。
....
I think it depends on what problems you are facing.
....
一些算法依赖于 DFS（或 BFS）的特定属性来工作。例如，用于查找 2 个连通分量的 Hopcroft 和 Tarjan 算法利用了 DFS 遇到的每个已访问节点都位于从根到当前探索节点的路径上的事实。
Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.
对于 BFS，我们可以考虑 Facebook 的例子。我们收到从其他朋友个人资料中添加 FB 个人资料中的朋友的建议。假设A->B，而B->E且B->F，那么A会得到E和F的建议。他们一定是使用BFS读到第二级。
DFS 更多地基于这样的场景：我们希望根据从源到目的地的数据来预测某些内容。正如已经提到的关于国际象棋或数独的内容。
一旦我在这里有不同的是，我相信 DFS 应该用于最短路径，因为 DFS 将首先覆盖整个路径，然后我们可以决定最好的路径。但由于 BFS 将使用贪婪的方法，因此它看起来可能是最短路径，但最终结果可能会有所不同。
请告诉我我的理解是否错误。
For BFS, we can consider Facebook example. We receive suggestion to add friends from the FB profile from other other friends profile. Suppose A->B, while B->E and B->F, so A will get suggestion for E And F. They must be using BFS to read till second level.
DFS is more based on scenarios where we want to forecast something based on data we have from source to destination. As mentioned already about chess or sudoku.
Once thing I have different here is, I believe DFS should be used for shortest path because DFS will cover the whole path first then we can decide the best. But as BFS will use greedy's approach so might be it looks like its the shortest path, but the final result might differ.
Let me know whether my understanding is wrong.
根据DFS和BFS的性质。
例如，当我们想要找到最短路径时。
我们通常使用bfs，它可以保证“最短”。
但dfs只能保证我们可以从这个点到达那个点，不能保证“最短”。
According to the properties of DFS and BFS.
For example,when we want to find the shortest path.
we usually use bfs,it can guarantee the 'shortest'.
but dfs only can guarantee that we can come from this point can achieve that point ,can not guarantee the 'shortest'.
由于深度优先搜索在处理节点时使用堆栈，因此 DFS 提供了回溯。由于广度优先搜索使用队列而不是堆栈来跟踪处理的节点，因此 BFS 不提供回溯。
Because Depth-First Searches use a stack as the nodes are processed, backtracking is provided with DFS. Because Breadth-First Searches use a queue, not a stack, to keep track of what nodes are processed, backtracking is not provided with BFS.
当树的宽度很大，深度很小时，使用DFS，因为递归栈不会溢出。当宽度很小，深度很大时，使用BFS来遍历树。
When tree width is very large and depth is low use DFS as recursion stack will not overflow.Use BFS when width is low and depth is very large to traverse the tree.
这是一个很好的例子，证明 BFS 在某些情况下比 DFS 更好。 https://leetcode.com/problems/01-matrix/
正确实施后，两者解决方案应该访问距离比当前单元格+1更远的单元格。
但 DFS 效率低下，并且会重复访问同一单元，导致复杂度为 O(n*n)。
例如，
This is a good example to demonstrate that BFS is better than DFS in certain case. https://leetcode.com/problems/01-matrix/
When correctly implemented, both solutions should visit cells that have farther distance than the current cell +1.
But DFS is inefficient and repeatedly visited the same cell resulting O(n*n) complexity.
For example,