【C/C++面试必备】bfs和dfs的区别

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

大家对 bfs 和 dfs 应该都有了解，都是很常用的搜索算法，本文结合实例来讲解下这两者的不同。

一、什么是 bfs ?

bfs 是 Breadth-First Search 的缩写，称为广度优先搜索，或宽度优先搜索。

1.1 搜索方式

步骤 1：从源点出发，访问源点的邻居结点，将邻居节点依次放入队列中，并标记为已访问；

步骤 2：取出队列中的邻居结点，依次访问每个节点未被访问的邻居节点；

步骤 3：将邻居节点依次放入队列中，并标记为已访问；

步骤 4：重复步骤 2~3 直到访问到目标节点或所有节点都标记为已访问。

来看一个简单的例子，下面是一个无向图：

使用广度优先搜索遍历上图，节点的访问顺序是（假设相同邻居节点优先访问编号小的节点）：

1 -> 2 -> 3 -> 5 -> 4 -> 6 -> 7

二、什么是 dfs ?

dfs 是 Depth-First-Search 的缩写，称为深度优先搜索。

2.1 搜索方式

步骤 1：从源点出发，访问源点的某个邻居节点，将其放入栈中，并标记为已访问；

步骤 2：从栈中取出一个节点，访问该节点的未被访问的邻居节点；

步骤 3：将邻居节点放入栈中，并标记为已访问；

步骤 4：重复步骤 2 ~ 3，直到访问到目标节点或所有节点都标记为已访问；

来看一个简单的例子，下面是一个无向图：

使用深度优先搜索遍历上图，节点的访问顺序是（假设相同邻居结点先访问编号小的节点）：

1->2->4（4 节点没有未访问的邻居结点返回到 2 节点）-> 5 -> 6->3->7

一般来说，bfs 和 dfs 在不同的场景下都有效，但是，采用的算法不同，程序执行的效果会有差异，应该选择合适的算法。

三、bfs 和 dfs 的区别

3.1 数据结构

bfs 遍历节点是先进先出，一般使用队列作为辅助数据结构，dfs遍历节点是先进后出，一般使用栈作为辅助数据结构；

3.2 访问节点的方式

bfs是按层次访问的，先访问源点，再访问它的所有相邻节点，并且标记结点已访问，根据每个邻居结点的访问顺序，依次访问它们的邻居结点，并且标记节点已访问，重复这个过程，一直访问到目标节点或无未访问的节点为止。

dfs 是按照一个路径一直访问到底，当前节点没有未访问的邻居节点时，然后回溯到上一个节点，不断的尝试，直到访问到目标节点或所有节点都已访问。

3.3 应用

bfs 适用于求源点与目标节点距离近的情况，例如：求最短路径。dfs 更适合于求解一个任意符合方案中的一个或者遍历所有情况，例如：全排列、拓扑排序、求到达某一点的任意一条路径。

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬