搜索算法-DFS&BFS

百度百科关于搜索算法的定义：搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。从定义可知，搜索算法本质是一种穷举算法，是列出所有的可能性。另一方面它也是一种有目的的搜索算法，所以在穷举的过程中需要进行剪枝来提高执行效率避免超时TLE。
搜索算法中常用的只要有两种算法：深度优先遍历(Depth-First-Search : DFS)和广度优先遍历(Breadth-First-Search : BFS)。
算法基础：BFS和DFS的直观解释用图的形式非常形象地概况出了两者在求解上的差异。通过该文对BFS和DFS有了模糊的认识。
仍然以上文的例子，如下图，灰色代表墙壁，绿色代表起点，红色代表终点。

BFS&DFS.png

BFS&DFS的异同及应用场景

BFS

广度优先搜索算法BFS是一种使用队列来保存中间状态并最终求解的算法，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。以走迷宫为例，最开始人在起点，首先把走一步能到的位置全都放在队列里，走一步所到达的位置全部放入完毕后，比如A，B两点，然后计算两步可以到达的位置，此时需要先从队列里取出头节点A，然后把A一走能走到的位置插入到队列中(假如是C、D)，然后再把B点取出，把B一步能走到的位置插入到队列中(假如是E、F)，此时队列变为C、D、E、F。此时队列中保存的是从起点两步可达的地方。以此类推。BFS就是利用队列先进先出的特性，把中间节点的信息保存在队列中，直到达到最优解。
使用场景：一般用于求解最优解，如最小步数，最短路径等，但是现在也会有些题目会给程序员挖坑，比如求解最大的解，这时候脑海中需要判断这个最优解是不是涟漪最先到达的位置，如果相反是最后到达的位置，使用BFS显然就不对了，会造成计算的空间复杂度高而使得内存爆掉。
特点：队列保存中间状态，状态的维护更新较为复杂，算法的空间复杂度高

DFS

深度优先搜索算法DFS是一种利用递归实现的搜索算法。其搜索过程和 “不撞南墙不回头” 类似。以走迷宫为例，DFS的走法是从起点一直走，假如从a-b-c-d，此时发现d点无路可走，需要退回c点继续走，假如是a-b-c-e-f，f是出口，就走出了迷宫。这个过程中就使用了递归技术。
使用场景：适合搜索全部的解，比如迷宫从起点走到终点的路径个数等等，这时显然需要遍历所有的解空间，而使用BFS需要记录很多的中间状态，使用DFS则不需要，使用递归非常简单的实现，空间复杂度低。
特点：空间复杂度低，递归效率差，可能爆栈

相同点

BFS和DFS在求解过程中，一般都需要剪枝，而剪枝的好坏决定了程序运行的性能，剪枝的策略有很多，需要根据题目进行思考，一般的剪枝策略包含：无效值剪枝、最优性剪枝等。
另外在BFS、DFS中一般需要记录状态的变化，如走迷宫，BFS需要记录当前位置是从起点走几步到的，如X点，可能走3 、4 、5步都可以到，但是只有第3步才有意义，因为第4、5步走的肯定不如第3步走到X点更优。在DFS走迷宫时，也需要记录该点是否走过。
状态的记录及剪枝对于算法非常重要。

代码模板

DFS代码模板

void dfs(depth，...) 
{  
    if(目标解)  //
    {  
        ...//记录当前全局状态信息到结果中  
        return;  
    }  

    for(...)//从当前状态扩展下一状态  
    {  
        if(非法状态 ) continue；
        if(剪枝条件) continue；
        修改全局状态变量；  
         dfs(depth+1, ...)；  
         还原全局状态变量；  
        }  
    }  
}  

BFS代码模板

void bfs() 
{  
    queue<Node> q;
    q.push(head); //将起点插入到列表中
    isvisited[head]=true; // 标记首节点已经被访问： 
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        for(...)//从当前状态扩展下一状态  
        {  
            if(非法状态 ) continue；
            if(剪枝条件)  continue；//比如被访问过
            Node next = ....;
            isvisited[next]=true;
            q.push(next);
    }
}  

关于BFS、DFS不太好用语言去描述，但是上面的这些思路有一定的指导意义，可以先试着做几道题目再回来看，相信你会有收获。

题目可以参考：
基本搜索算法(DFS|BFS)
后面我也会根据时间更新些典型代码。

WalkeR-ZG