dfs与bfs的套路总结

为了我亲爱的鸽鸽！
致敬！

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模板吧。不过其实很容易就看明白了。
白版纯手打代码，这个格式和空格和制表符好难搞，难受得不行。
就这样吧，先假装写完啦~~~