广度优先或深度优先搜索
我知道这个算法是如何工作的，但无法决定何时使用哪种算法？
是否有一些指导方针，其中一个比其他人表现更好或有任何考虑因素？
非常感谢。
I know how this algorithm works, but cant decide when to use which algorithm ?
Are there some guidelines, where one better perform than other or any considerations ?
Thanks very much.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您想找到步数最短的解决方案，或者您的树具有无限高度（或非常大），您应该首先使用广度。
如果您有一棵有限树并且想要使用最小的内存量遍历所有可能的解决方案，那么您应该首先使用深度。
如果您正在寻找最佳的国际象棋走法，您可以使用迭代深化，这是一个两者的结合。
If you want to find a solution with the shortest number of steps or if your tree has infinite height (or very large) you should use breadth first.
If you have a finite tree and want to traverse all possible solutions using the smallest amount of memory then you should use depth first.
If you are searching for the best chess move to play you could use iterative deepening which is a combination of both.
当图形具有一些有意义的“自然分层”（例如，较近的节点表示“较接近”的结果）并且您的目标结果可能更接近起点或起点“搜索成本较低”时，BFS 通常很有用。 ”。
当你想找到最短路径时，BFS是自然的选择。
如果您的图是无限的或通过编程生成的，您可能希望在冒险之前搜索更近的层，因为在到达更近的节点之前探索远程节点的成本是令人望而却步的。
如果由于内存/磁盘/位置问题访问更多远程节点的成本更高，那么 BFS 可能会更好。
BFS is generally useful in cases where the graph has some meaningful "natural layering" (e.g., closer nodes represent "closer" results) and your goal result is likely to be located closer to the starting point or the starting points are "cheaper to search".
When you want to find the shortest path, BFS is a natural choice.
If your graph is infinite or pro grammatically generated, you would probably want to search closer layers before venturing afield, as the cost of exploring remote nodes before getting to the closer nodes is prohibitive.
If accessing more remote nodes would be more expensive due to memory/disk/locality issues, BFS may again be better.
使用哪种方法通常取决于应用程序（即必须搜索图的原因） - 例如拓扑排序需要深度优先搜索，而寻找最大流的 Ford-Fulkerson 算法需要广度优先搜索。
Which method to use usually depends on application (ie. the reason why you have to search a graph) - for example topological sorting requires depth-first search whereas Ford-Fulkerson algorithm for finding maximum flow requires breadth-first search.
如果您正在遍历一棵树，深度优先将使用与其深度成比例的内存。如果树是相当平衡的（或者对其深度有一些其他限制），那么使用递归深度优先遍历可能会很方便。
但是，不要在遍历一般图时这样做；它可能会导致堆栈溢出。对于无界树或一般图，您将需要某种可以扩展到与输入节点数量成比例的大小的辅助存储。这种情况下，广度优先遍历就简单方便了。
如果您的问题提供了选择一个节点而不是另一个节点的理由，您可以考虑使用优先级队列，而不是堆栈（对于深度优先）或 FIFO（对于广度优先）。优先级队列将花费 O(log K) 时间（其中 K 是当前不同优先级的数量）来找到每一步的最佳节点，但优化可能是值得的。
If you are traversing a tree, depth-first will use memory proportional to its depth. If the tree is reasonably balanced (or has some other limit on its depth), it may be convenient to use recursive depth-first traversal.
However, don't do this for traversing a general graph; it will likely cause a stack overflow. For unbounded trees or general graphs, you will need some kind of auxiliary storage that can expand to a size proportional to the number of input nodes. In this case, breadth-first traversal is simple and convenient.
If your problem provides a reason to choose one node over another, you might consider using a priority queue, instead of a stack (for depth-first) or a FIFO (for breadth-first). A priority queue will take O(log K) time (where K is the current number of different priorities) to find the best node at each step, but the optimization may be worth it.