为了我亲爱的鸽鸽！
致敬！
dfs和bfs，顾名思义就是，深度优先搜索和广度优先搜索的简称。那么什么是深度优先什么是广度优先？
举个简单的例子吧。
比如说电话的9键中。
2--a,b,c
3--d,e,f
4--g,h,i
……
有着这样的对应关系。
那么当我依次按下，2,3,4的时候，一共会有多少种组合呢？
首先我们用深度优先搜索的思路来讲。
深度优先，就是每次都会遍历得到一个结果，并将其放入结果集合中。每次都要走到无路可走，才知道回头。
最直观的反映，让我们来看结果集的样子。它会是这样增加的：
[{a,d,g}]-->[{a,d,g},{a,d,h}]-->[{a,d,g},{a,d,h},{a,d,i}]-->[{a,d,g},{a,d,h},{a,d,i},{a,e,g}]……
先找到一个结果，然后通过回溯查找，每次都在集合中增加一个可达结果。
为了迅速找到不同，接下来我们用广度优先搜索的思路来讲。
广度优先，逐层遍历，当把第一层所有情况都记录下以后，再进行第二层的遍历。
最直观的反映在结果集的样子。它会是这样增加的：
[{a},{b},{c}]-->
[{a,d},{a,e],{a,f}]-->[{a,d},{a,e],{a,f},{b,d},{b,e},{b,f}]-->[{a,d},{a,e],{a,f},{b,d},{b,e},{b,f},{c,d},{c,e},{c,f}]-->
[{a,d,g},{a,d,h},{a,d,i}……]
每次都在之前已有记录的基础上，遍历当前行拼接之后的所有情况。
一般来说，这种找到【组合】类型，获得【所有结果】，列出【所有情况】的题目，就可以考虑使用这两种解法。【贪心，动归等不要杠精，我只是说暴搜解而已】
那么，他们分别更加适用的场景是什么呢？
我们观察和思考了算法之后，很容易想到，当结果集庞大，每个最终结果的深入层次比较浅时，或者只需求最终结果时，选择bfs更快更方便；当每个最终结果都需要寻觅非常深入，或者存在回溯查找时，选择dfs会更好。
毕竟，广度优先和深度优先的名字摆在这里。自然是在得意领域更加肆意了。
好的，我们看下它们的必要条件：可重复利用上一次的结果 || 需要当前结果的状态 || 需要记录当前结果||需要记录所有已知情况
需要之前的状态和结果记录啊。也就是说可以选择用递归的方式。
而且，其实dfs和bfs的代码真的很有套路。基本上你确定了用哪一个之后，就可以套用类似模板的写法了。干倒一般性难度的题目不成问题。
回归本质，我们用这道题简化版来举个例子：
如图，二维数组，从每个子数组中取出一个值，找到所有排列组合。
String arr =
{{a,b,c},
{d,e,f},
{g,h,i}}
//dfs模式样板
public class solution{
public List<List<String>> getResult(String[][] arr){
//第一行，定义结果集合
List<List<String>> result = new ArrayList<List<String>>();
//第二行，定义每次单独产生的结果
List<String> temp = new ArrayList<String>();
//第三行，传入第一次dfs的条件（空的结果数组，空的tmp，开始深度0，目标数组），通过dfs拿到最终的结果。
dfs(result,temp,0);
//第四行，返回结果
return result；
}
//dfs的逻辑
public void dfs(List<List<String>> result,List<String> temp,int depth){
//递归出口。返回条件-->找到一个有效结果（或者说，一条道走到死，走到无路可走，最深处）
if(arr.length() == depth){
//将当前结果添加到结果集合中
result.add(new ArrayList<String>(temp)）;
//如果查找到一条结果，则回溯到上个状态
return;
}else{
//dfs相当于用depth这个参数做了外层的，也就是深度的控制，让你每次都更加向内走
for(int i = 0;i<arr[depth].length;i++){
//添加当前深度的当前字符
temp.add(arr[depth][i]);
//带着当前的中间态结果temp去下一层，直到找到最深一层。然后记录结果。return当前调用。
dfs(result,temp,depth+1);
//举例来说：第一次搜索后得到的结果是[a,d,g]，此时深度为目标深度，因此，记录结果到result中，然后return。
//此时回到**dfs(result,temp,depth+1);**这一句。此时depth为1，也就是倒数第二层。temp中有[a,d,g]三个对象，result中有一条记录[[a,d,g]]。然后，我们删掉最后的对象g，让temp为[a,d]的状态，来到当前深度的第二个字符面前。
temp.remove(temp.size()-1);
//然后temp会变成[a,d,h]，然后再进入最后一层。然后再记录到result中，然后再回到倒数第二层。以此类推。
}
}
}
所以当最后dfs遍历完成后，result数组中就保存了所有结果。
有没有稍微明白一点点了呢？
所有的dfs基本都是这样的套路。
//结果函数
solution(){
//最终结果集
new resultSets;
//单个结果
new resultOne;
//初始调用dfs
dfs(resultSets,resultOne,0);
return result;
}
dfs(T<M> resultSets,M resultOne, int depth){
//递归出口
if(depth == 最深){
//这里每一次的单个结果都需要new一次
resultSets.add(new resultOne);
//回溯
return;
}else{
//当前深度的数据数据获取
for(int i = 0;i<arr[depth],length;i++){
//记录当前深度的当前下标的数据
resultOne.add(arr[depth][i]);
//寻找下一层
dfs(resultSets,resultOne,depth+1);
//清除下一层的对象数据
resultOne.remove(resultOne.size()-1);
}
}
}
好的，接下来是bfs，同样的题目。
我们来看bfs
class Solution {
public List<List<String>> getResult(String[][] arr){
//第一行，定义结果集合
List<List<String>> result = new ArrayList<List<String>>();
//第三行，使用广度优先搜索的方式
result = bfs(result,0);
//第四行，返回结果
return result；
}
public List<List<String>> bfs(List<List<String>> result,int depth){
//递归出口
if(depth==arr.length){
return;
}else{
List<List<String>> tempResult = new ArrayList<List<String>>();
//不是第一行了，循环遍历，补充结果集
if(result.size()>0){
for(List<String> temp:result){
for(int i = 0;i<arr[depth].length;i++){
tempResult.add(temp.add(arr[depth][i]));
}
}
}else{
//第一次遍历，初始化结果集，添加第一层的值
for(int i = 0;i<arr[depth].length;i++){
tempResult.add(new ArrayList(arr[depth][i]));
}
}
bfs(tempResult,depth+1);
}
}
好困啊···明天再整理bfs模板吧。不过其实很容易就看明白了。
白版纯手打代码，这个格式和空格和制表符好难搞，难受得不行。
就这样吧，先假装写完啦~~~
网友评论