广度优先搜索(也称为BFS)是用于扩展特定图形的所有节点的搜索方法。它通过搜索每个解决方案以检查和扩展这些节点(或其中的序列组合)来完成此任务。因此，BFS不使用启发式算法(或通过多个场景搜索解决方案的算法)。获取所有节点后，将它们添加到称为先进先出队列的队列中。那些尚未浏览的节点被“存储”在标记为“打开”的容器中；一经探索，它们便被运送到标有“封闭”的容器中。
深度优先搜索(也称为DFS)是一种搜索方法，可深入到搜索的子节点中，直到达到目标为止(或直到存在没有任何其他排列或“子项”的节点)为止。找到一个目标后，搜索将回溯到已解决方案的上一个节点，重复此过程，直到成功搜索了所有节点。因此，节点继续被留作进一步探索–这称为非递归实现。
BFS的功能是时间和空间复杂性，完整性，完整性证明和最优性。空间复杂度是指在搜索的最深层中节点数的比例。时间复杂度是指用于考虑节点在搜索中采用的每条路径的实际“时间”量。本质上，完整性是一种在图形中查找解决方案的搜索，而不管其是哪种图形。完整性的证明是在确定深度的节点中找到目标的最浅层次。最后，最优性是指未加权的BFS – 这是用于单位成本的图表。
FS是使用生成树的最自然的输出 - 生成树是由无向图中的所有顶点和某些边组成的树。 在这种形式中，图分为三类:从节点指向子节点的前向边缘； 从节点指向较早节点的后边缘； 和交叉边缘，它们都不是其中之一。
总结
- BFS搜索图中的每个解决方案以扩展其节点； DFS深入子节点内，直到达到目标为止。
- BFS的特征是时空复杂性，完整性，完整性证明和最优性； DFS最自然的输出是具有三类的生成树:前边缘，后边缘和交叉边缘。
欢迎任何形式的转载，但请务必注明出处，尊重他人劳动成果。
转载请注明：文章转载自 有区别网 [http://www.vsdiffer.com]
本文标题：BFS和DFS
本文链接：https://www.vsdiffer.com/vs/bfs-vs-dfs.html
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。