首先这两个概念应该都是算法上的，这个没啥疑问。
先用官方的说法说一下两者的区别：
DFS（Deep First Search）深度优先搜索。
BFS（Breath First Search）广度优先搜索。
至于说所谓的深度和广度，让我们用"人话"来理解一下：
什么是DFS深度优先搜索？
用一个常用的思路来表述：递归就是一个标准的深度搜索。一层一层往下走。但是有些时候在算法中经常会遇到一条路走不通的情况，那么我们就返回上一层换条路走。
拿一个游戏作比喻：假如有一个迷宫，其方式是一层门一层门的往里走，目标是最终走出这个迷宫。具体的游戏方式起始房间有9个门，我们可以任选其一进入，下一个房间也会有9个门，直到最后一层会要么有出去的大门，要么是一堵墙。
在不开挂的情况下想要走出这个迷宫通常情况下只能一个个试，一层层往下随机走，直到最后一层如果出去了就出去了，但是如果没出去那么返回上一层，继续碰运气。
用数学的思维来讲：起始房间是最开始的那个，也就是度是0的那个。而往下走的话下一个房间是度是1的，下下一个房间是度是2的。依次类推。。
而如果真有这么个题目，我们也可以用递归+回溯的方式来实现。
所以说我们常用的递归，回溯都属于DFS，也就是深搜。
而深搜通常是可以知道我们能不能做到某事，而广搜一般还能知道做到某事的最小路径。
什么是BFS广度优先搜索？
相对于DFS的一层一层往深了去走，广搜更像是每一层每一个选择都选了。依旧拿那个游戏做例子：我们可以在起始入口就分出9个线程，都走一遍。往下也是依次这样，反正人多呗。
刚刚讲的迷宫，不管是深搜还是广搜，我们都可以得到答案，而两者的优缺点：
深搜可以告诉我们能不能过，而且只需要一个人去挨个尝试。
广搜不仅告诉我们能不能过，而且还可以把所有能过的路线都记录下来，甚至还可以有很多附加的功能：比如说能通过的门牌号最小的路径，最靠左/右的路径等等。但是相对于深搜是要更加复杂一点的。
当然了，上面是很简单的说法，比如说深搜也可以在找到通过的路径以后不出去继续挨个试。
毕竟两种搜索方法本质都是穷竭列举所有的情况。
实际选择哪种方法
我们在具体是算法题目上选择哪种搜索方法还是要结合实际的，比如我上面说的如果问题是能不能，那么深搜大部分就可以满足了，但是如果涉及到了最短/最小/最大等，广搜比较适合。
形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。
其实我觉得两者的应用场景差不多：都是在不断的做选择的情境下使用，下面简单出两个比较有针对性的题目：
题目
这个题虽然很简单，但是可以很直观的表示深搜和广搜的用法区别了。比如第一个问题，能不能达到50分，我们可以采用深搜的方式，递归往下走，正常先都走第一个结果：12+3+7+56 = 78.
因为78>50.所以结果是有可能得到50分，这个题就做完了。（当然了这个是最好的情况，如果第一条路不行，那么要回退上一步，换一条往下走，比如12+3+7+44.再不行就是12+3+7+8...深搜的最坏结果就是变成了广搜）
但是第二个问题，最大获取多少分，那么就要每一条路都走一遍，获取其中最大的值，那么这种方式就是广搜。
代码书写思路
因为我是java开发，所以这里简单说一下两个搜索方式在java中实现：
DFS深度优先搜索：一个标准使用方式就是递归。而递归其实就是隐式栈，所以我们也可以用显式栈来实现。这里栈的先进后出其实是实现回退上一步的方式。不管是显示栈调用还是隐式的方法递归都可以。
BFS广度优先搜索：这个咋说呢，每一层都记录，每一条路走要走一遍，其实用队列就可以了。
当然了具体的代码书写就更复杂了，要根据情况来写，所以我这里也不班门弄斧了。两个常用模板：
回溯模板：
public boolean dfs(int[] n) {
//所有可能性
for(int i:n) {
//1. 选择当前可能
//2. 递归(注意如果到了最后一层并且是boolean判断，结果是true可以直接返回结果)
//3. 回退上一步(走到这一步就说明之前的路不通)
}
//正常来讲如果走到这一步说明全都遍历一遍也没能通过的路，所以直接false
return false;
}
其实我上面写的比较有局限，并不一定都是boolean的结果，反正我这里就是举个例子。反正标准三步走：添加 递归 回溯 是没什么问题的。
深搜模板：
深搜这里有个问题，比如我之前说的是单向的，所以直接往下挨个试，但是有些时候无向的就不好处理的，比如立体迷宫之间是相互的，A房间的第一个门是B，B房间第一个门是A，这样的关系，A->B->A->B，死循环了，所以这种的要有限制：不能走回头路。下面是标准模板：
public void bfs() {
Queue<String> q = new LinkedList<String>(); // 核心数据结构
Set<String> visited = new HashSet<String>(); // 避免走回头路
//从起始开始，所有能选择的都要选
q.offer("开始"); // 将起点加入队列
visited.add("开始");
int step = 0; // 如果需要记录最小操作步骤
while(!q.isEmpty()) {//当前有可选项
int sz = q.size();
//可选的选择都选一遍
for (int i = 0; i < sz; i++) {
String cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur.equals("出口")) {
//走到这说明当前线路已经走通了，可以做一些具体的逻辑
//如果是最短路径的话，那么到当前肯定是最短的了可以直接返回
}
/* 将 cur 的下一步加入队列 */
//这里记得要把访问过的记录，防止重复走
}
// 划重点：一层队列中步数一样
step++;
}
}
写了以后我才发现哪有那么多现成的模板啊，都要根据实际情况来做，我这个模板写的不伦不类的，但是我尽量注解写的挺全了，如果用的话，根据实际情况应变吧。
这篇笔记中关于DFS和BFS的概念，思路还有一些个人理解就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！ps：因为我完全是野路子出身的，如果某些概念或者用词不准确欢迎指出！
网友评论