BFS 与 DFS – 它们之间的区别

什么是 BFS？

BFS 是一种用于绘制数据图或搜索树或遍历结构的算法。该算法以精确的广度方式高效地访问并标记图中的所有关键节点。

该算法选择图中的单个节点（初始点或源点），然后访问所选节点的所有相邻节点。一旦算法访问并标记起始节点，它就会移动到最近的未访问节点并对其进行分析。

一旦访问过，所有节点都会被标记。这些迭代持续进行，直到图中的所有节点都已成功访问并标记。BFS 的完整形式是广度优先搜索。

什么是 DFS？

DFS 是一种沿深度方向查找或遍历图或树的算法。该算法的执行从根节点开始，并在回溯之前探索每个分支。它使用堆栈数据结构来记住、获取后续顶点以及在任何迭代中出现死胡同时开始搜索。DFS 的全称是深度优先搜索。

BFS 和 DFS 二叉树之间的区别

以下是 BFS 和 DFS 之间的重要区别。

BFS	DFS
BFS 找到到达目的地的最短路径。	DFS 到达子树的底部，然后回溯。
BFS 的全称是广度优先搜索。	DFS 的全称是深度优先搜索。
它使用队列来跟踪下一个要访问的位置。	它使用堆栈来跟踪下一个要访问的位置。
BFS按照树的层级进行遍历。	DFS按照树的深度进行遍历。
它是使用FIFO列表实现的。	它是使用 LIFO 列表实现的。
与 DFS 相比，它需要更多的内存。	与 BFS 相比，它需要的内存更少。
该算法给出了最浅路径解决方案。	该算法不保证最浅路径解决方案。
BFS中不需要回溯。	DFS中需要回溯。
您永远不会陷入有限循环。	您可能会陷入无限循环。
如果您没有找到任何目标，您可能需要扩展许多节点才能找到解决方案。	如果没有找到任何目标，则可能会发生叶节点回溯。

BFS 示例

在下面的 BFS 示例中，我们使用了具有 6 个顶点的图。

BFS 示例

步骤1）

您有一张包含 0 – 6 之间的七个数字的图表。

步骤2）

0 或零已被标记为根节点。

步骤3）

0 被访问、标记并插入到队列数据结构中。

步骤4）

剩余 0 个相邻且未访问的节点被访问、标记并插入到队列中。

步骤5）

重复遍历迭代，直到访问所有节点。

DFS 示例

在下面的 DFS 示例中，我们使用了一个具有 5 个顶点的无向图。

步骤1）

我们从顶点 0 开始。算法首先将其放入访问列表中，同时将其所有相邻顶点放入 数据结构 称为堆栈。

步骤2）

您将访问位于堆栈顶部的元素（例如 1），然后转到其相邻节点。这是因为 0 已经被访问过。因此，我们访问顶点 2。

步骤3）

顶点 2 在 4 中有一个未访问的附近顶点。因此，我们将其添加到堆栈中并访问它。

步骤4）

最后，我们将访问最后一个顶点 3，它没有任何未访问的相邻节点。我们已经使用 DFS 算法完成了图的遍历。

BFS 的应用

以下是 BFS 的应用：

非加权图

BFS 算法可以轻松创建最短路径和最小生成树，以最短的时间和高精度访问图的所有顶点。

P2P 网络

可以实施 BFS 来定位对等网络中所有最近或相邻的节点。这样可以更快地找到所需的数据。

网络爬虫

搜索引擎 或者网络爬虫可以通过使用 BFS 轻松构建多级索引。BFS 实现从源（即网页）开始，然后访问来自该源的所有链接。

网络广播

广播数据包由 BFS 算法引导，查找并到达其具有地址的所有节点。

DFS 的应用

以下是DFS的重要应用：

加权图

在加权图中，DFS 图遍历生成最短路径树和最小生成树。

检测图中的循环

如果在 DFS 过程中我们发现了回边，则该图存在循环。因此，我们应该对图运行 DFS 并验证回边。

寻找路径

我们可以专门使用 DFS 算法来搜索两个顶点之间的路径。

拓扑排序

它主要用于根据给定的依赖关系对作业组进行调度。在计算机科学中，它用于指令调度、数据序列化、逻辑综合、确定编译任务的顺序。

搜索图中的强连通分量

当图中的每个顶点都有一条路径到其他剩余顶点时，它用于 DFS 图。

解决只有一个解决方案的难题

DFS 算法可以通过在访问集中包含现有路径上的节点来轻松适应搜索迷宫的所有解决方案。