BFS 和 DFS 的区别

在了解 BFS 和 DFS 的区别之前，我们首先应该分别了解 BFS 和 DFS。

什么是 BFS？

BFS 代表 **广度优先搜索**。它也称为 **层序遍历**。队列数据结构用于广度优先搜索遍历。当我们在图中对 BFS 算法进行遍历时，可以将任何节点视为根节点。

让我们考虑下面的图来进行广度优先搜索遍历。

假设我们将节点 0 视为根节点。因此，遍历将从节点 0 开始。

一旦节点 0 从队列中移除，它就会被打印并标记为 **已访问节点**。

一旦节点 0 从队列中移除，节点 0 的相邻节点将插入队列，如下所示：

现在，节点 1 将从队列中移除；它将被打印并标记为已访问节点。

一旦节点 1 从队列中移除，节点 1 的所有相邻节点都将添加到队列中。节点 1 的相邻节点是 0、3、2、6 和 5。但我们必须只将未访问的节点插入队列。由于节点 3、2、6 和 5 均未访问；因此，这些节点将被添加到队列中，如下所示：

队列中的下一个节点是 3。因此，节点 3 将从队列中移除，打印并标记为已访问，如下所示：

一旦节点 3 从队列中移除，节点 3 的所有相邻节点（已访问节点除外）都将添加到队列中。节点 3 的相邻节点是 0、1、2 和 4。由于节点 0、1 已被访问，而节点 2 存在于队列中；因此，我们只需要将节点 4 插入队列。

现在，队列中的下一个节点是 2。因此，2 将从队列中删除。它将被打印并标记为已访问，如下所示：

一旦节点 2 从队列中移除，节点 2 的所有相邻节点（已访问节点除外）都将添加到队列中。节点 2 的相邻节点是 1、3、5、6 和 4。由于节点 1 和 3 已被访问，而 4、5、6 已被添加到队列中；因此，我们不需要将任何节点插入队列。

下一个元素是 5。因此，5 将从队列中删除。它将被打印并标记为已访问，如下所示：

一旦节点 5 从队列中移除，节点 5 的所有相邻节点（已访问节点除外）都将添加到队列中。节点 5 的相邻节点是 1 和 2。由于两个节点都已被访问；因此，没有顶点需要插入队列。

下一个节点是 6。因此，6 将从队列中删除。它将被打印并标记为已访问，如下所示：

一旦节点 6 从队列中移除，节点 6 的所有相邻节点（已访问节点除外）都将添加到队列中。节点 6 的相邻节点是 1 和 4。由于节点 1 已被访问，而节点 4 已被添加到队列中；因此，没有顶点需要插入队列。

队列中的下一个元素是 4。因此，4 将从队列中删除。它将被打印并标记为已访问。

一旦节点 4 从队列中移除，节点 4 的所有相邻节点（已访问节点除外）都将添加到队列中。节点 4 的相邻节点是 3、2 和 6。由于所有相邻节点都已被访问；因此，没有顶点需要插入队列。

什么是 DFS？

DFS 代表 **深度优先搜索**。在 DFS 遍历中，使用栈数据结构，它遵循 LIFO（后进先出）原则。在 DFS 中，遍历可以从任何节点开始，或者我们可以说，只要问题中没有提及根节点，任何节点都可以被视为根节点。

在 BFS 的情况下，从队列中删除的元素，被删除节点的相邻节点会被添加到队列中。相反，在 DFS 中，从栈中移除的元素，只会被删除节点的其中一个相邻节点添加到栈中。

让我们考虑下面的图来进行深度优先搜索遍历。

将节点 0 视为根节点。

首先，我们将元素 0 插入栈，如下所示：

节点 0 有两个相邻节点，即 1 和 3。现在我们可以只选择一个相邻节点，1 或 3，进行遍历。假设我们选择节点 1；因此，1 被插入栈并被打印，如下所示：

现在我们将查看节点 1 的相邻顶点。节点 1 的未访问相邻顶点是 3、2、5 和 6。我们可以选择这四个顶点中的任何一个。假设我们选择节点 3 并将其插入栈，如下所示：

考虑节点 3 的未访问相邻顶点。节点 3 的未访问相邻顶点是 2 和 4。我们可以选择任一顶点，即 2 或 4。假设我们选择顶点 2 并将其插入栈，如下所示：

节点 2 的未访问相邻顶点是 5 和 4。我们可以选择任一顶点，即 5 或 4。假设我们选择顶点 4 并将其插入栈，如下所示：

现在我们将考虑节点 4 的未访问相邻顶点。节点 4 的未访问相邻顶点是节点 6。因此，元素 6 被插入栈，如下所示：

将元素 6 插入栈后，我们将查看节点 6 的未访问相邻顶点。由于节点 6 没有未访问的相邻顶点，因此我们无法超出节点 6。在这种情况下，我们将执行 **回溯**。栈顶元素，即 6，将被弹出栈，如下所示：

栈顶元素是 4。由于节点 4 没有剩余未访问的相邻顶点；因此，节点 4 被弹出栈，如下所示：

栈中的下一个顶部元素是 2。现在，我们将查看节点 2 的未访问相邻顶点。由于只剩下一个未访问的节点，即 5，因此节点 5 将被推到 2 之上的栈中并被打印，如下所示：

现在我们将查看节点 5 的仍然未访问的相邻顶点。由于没有剩余的顶点需要访问，因此我们将元素 5 从栈中弹出，如下所示：

我们无法进一步访问 5，因此我们需要执行回溯。在回溯中，栈顶元素将被弹出。栈顶元素是 5，它将被弹出栈，我们将返回到节点 2，如下所示：

现在我们将查看节点 2 的未访问相邻顶点。由于没有剩余的相邻顶点需要访问，因此我们执行回溯。在回溯中，栈顶元素，即 2，将被弹出栈，我们将返回到节点 3，如下所示：

现在我们将查看节点 3 的未访问相邻顶点。由于没有剩余的相邻顶点需要访问，因此我们执行回溯。在回溯中，栈顶元素，即 3，将被弹出栈，我们将返回到节点 1，如下所示：

弹出元素 3 后，我们将查看节点 1 的未访问相邻顶点。由于没有剩余的顶点需要访问；因此，将执行回溯。在回溯中，栈顶元素，即 1，将被弹出栈，我们将返回到节点 0，如下所示：

我们将查看节点 0 的仍然未访问的相邻顶点。由于没有剩余的相邻顶点需要访问，因此我们执行回溯。在此过程中，栈中只剩一个元素，即 0，将被弹出栈，如下所示：

正如我们从上图可以观察到的，栈是空的。因此，我们必须在这里停止 DFS 遍历，而被打印的元素就是 DFS 遍历的结果。

BFS 和 DFS 之间的区别

以下是 BFS 和 DFS 之间的区别：