c++ - 广度优先或深度优先搜索

Question

我知道这个算法是如何工作的，但无法决定何时使用哪种算法？

是否有一些指导方针，其中一个比其他或任何考虑更好？

非常感谢。

score 17 · Accepted Answer

如果您想找到步数最短的解决方案，或者如果您的树具有无限高（或非常大），您应该首先使用广度。

如果您有一棵有限树并且想要使用最少的内存遍历所有可能的解决方案，那么您应该首先使用深度。

如果您正在寻找最佳的国际象棋走法，您可以使用迭代深化，这是两者的结合。

IDDFS 结合了深度优先搜索的空间效率和广度优先搜索的完整性（当分支因子有限时）。

score 1 · Accepted Answer

BFS 通常在图形具有一些有意义的“自然分层”（例如，更近的节点表示“更接近”的结果）并且您的目标结果可能更靠近起点或起点“搜索更便宜”的情况下很有用”。

当你想找到最短路径时，BFS 是一个很自然的选择。

如果您的图表是无限的或以编程方式生成的，您可能希望在冒险之前搜索更近的层，因为在到达更近的节点之前探索远程节点的成本是令人望而却步的。

如果由于内存/磁盘/位置问题而访问更多的远程节点会更加昂贵，那么 BFS 可能会更好。

score 1 · Accepted Answer

使用哪种方法通常取决于应用程序（即您必须搜索图的原因） - 例如，拓扑排序需要深度优先搜索，而用于查找最大流量的 Ford-Fulkerson 算法需要广度优先搜索。

score 0 · Accepted Answer

如果您正在遍历一棵树，深度优先将使用与其深度成正比的内存。如果树是合理平衡的（或对其深度有一些其他限制），则使用递归深度优先遍历可能会很方便。

但是，不要为了遍历一般图而这样做；它可能会导致堆栈溢出。对于无界树或一般图，您将需要某种可以扩展至与输入节点数量成比例的大小的辅助存储。在这种情况下，广度优先遍历简单方便。

如果您的问题提供了选择一个节点而不是另一个节点的理由，您可能会考虑使用优先级队列，而不是堆栈（深度优先）或 FIFO（广度优先）。优先级队列将花费 O(log K) 时间（其中 K 是当前不同优先级的数量）来在每一步找到最佳节点，但优化可能是值得的。

4 回答 4