BFS和DFS的一些例题
深度优先搜索（Depth-First Search,DFS）和广度优先搜索（Breadth-First Search,BFS或者称为宽度优先搜索）是基本的暴力技术，常用于解决图、树的遍历问题。
首先考虑算法思路。以老鼠走迷宫为例，这是DFS和BFS在现实中的模型。在迷宫内部的路错综复杂，老鼠从入口进去后怎么才能找到出口？有两种不同的方法：
（1）一只老鼠走迷宫。它在每个路口都选择先走右边（当然，选择先走左边也是可以的），能走多远就走多远，知道碰壁无法继续往前走，然后回退一步，这一次走左边，接着往下走。用这个办法能走遍所有的路，而且不会重复（这里规定回退不算重复走）。这个思路就是DFS。
（2）一群老鼠走迷宫。假设老鼠是无限多的，这群老鼠进去后，在每个路口排出部分老鼠探索所有没走过的路。走某条路的老鼠，如果碰壁无法前行，就停下；如果到达的路口已经有其他老鼠探索过了，也停下。很显然，所有的道路都会走到，而且不会重复。这个思路就是BFS。BFS看起来像“并行计算”，不过，由于程序是单机顺序运动的，所以可以把BFS看成是并行计算的模拟。
在具体编程时，一般用队列这种数据结构来具体实现BFS，甚至可以说“BFS=队列”；对于DFS，也可以说“DFS=递归”，因为用递归实现DFS是最普遍的。DFS也可以用“栈”这种数据结构来直接实现，栈和递归在算法思想上是一致的。
例题：
HDU1312 Red and Black(黑红砖块)
题目大意： 有一个长方形的房间，铺满了正方形瓷砖。每个瓷砖都是红色或黑色的。一个人站在一块黑色的瓷砖上。从一个瓷砖上，他可以移动到四个相邻（上下左右）的瓷砖中的一个。但是他不能移动到红色的瓷砖，只能在黑色的瓷砖上移动。通过重复上面描述的动作，编写一个程序来计算他能达到的黑瓷砖的数量。
输入： 多个数据。第一行给出两个数m,n（0，0代表结束输入）；m代表列，n代表行。m,n均不超过20。对每一块瓷砖，填入“@”代表人站的初始位置（黑砖），“.”代表黑色砖，“#”代表红色砖.
输出： 输出人能踩过的黑色砖的总数（第一块人站的那个也算）。
解题思路：
这道题目跟老鼠走迷宫差不多：“#”相当于不能走的陷阱或墙壁，“.”是可以走的路。下面按“一群老鼠走迷宫”的思路编程。
要遍历所有可能的点，可以这样走：从起点1出发，走到它所有的邻居2、3；逐一处理每个邻居，例如在邻居2上，再走它的所有邻居4、5、6；继续以上过程，知道所有点都被走到，如下图所示。这是一个“扩散”的过程，如果把搜索空间看成一个池塘，丢一颗石头到起点位置，激起的波浪会一层层扩散到整个空间。需要注意的是，扩散按从近到远的顺序进行，因此，从每个被扩散到的点到起点的路径都是最短的。这个特征对解决迷宫这样的最短路径问题很有用。
用队列来处理这个扩散过程非常清晰、易懂。
（a）1进队，当前队列是{1}
（b）1出队，1的邻居是2、3进队，当前队列是{2，3}
（c）2出队，2的邻居是4、5、6进队，当前队列是{3，4，5，6}
（d）3出队，7，8进队，当前队列是{4，5，6，7，8}
（e）4出队，9进队，当前队列是{5，6，7，8，9}
（f）5出队，10进队，当前队列是{6，7，8，9，10}
（g）6出队，11进队，当前对列是{7，8，9，10，11}
（h）7出队，12、13进队，当前队列是{8，9，10，11，12，13}
（i）8、9出队，10出队，14进队，当前队列是{11，12，13，14}
（j）11出队，15进队，当前队列是{12，13，14，15}
（k）12，13，14，15出队，当前队列是空{}，结束。
程序实现
#include <bits/stdc++.h>
using namespace std;
char room[23][23];
int dir[4][2]={
{-1,0},//向左，左上角的坐标是（0，0）
{0,-1},//向上
{1,0},//向右
{0,1}//向下
};
int Wx,Hy,num;//WX行,Hy列用num统计可走的位置有多少
#define CHECK(x,y) (x<Wx && x>=0 && y<Hy && y>=0)//是否在room中
struct node{
int x,y;
};
void BFS(int dx,int dy){
num=1;//起点也包含在砖块内
queue<node> q;//队列中放坐标点
node start,next;
start.x=dx;
start.y=dy;
q.push(start);
while(!q.empty()){
start=q.front();
q.pop();
for(int i=0;i<4;i++){//按左上右下四个方向顺时针逐一搜查
next.x=start.x+dir[i][0];
next.y=start.y+dir[i][1];
if(CHECK(next.x,next.y) && room[next.x][next.y]=='.'){
room[next.x][next.y]='#';//进队之后标记为已经处理过
num++;
q.push(next);
}
}
}
}
int main(){
int x,y,dx,dy;
while(cin>>Wx>>Hy){//Wx行 Hy列
if(Wx==0 && Hy==0){//结束
break;
}
for(y=0;y<Hy;y++){//有Hy列
for(x=0;x<Wx;x++){//一次读入一行
cin>>room[x][y];
if(room[x][y]=='@'){//读入起点
dx=x;
dy=y;
}
}
}
num=0;
BFS(dx,dy);
cout<<num<<endl;
}
return 0;
}
关于hdu1312题还有另外一种解决方案，即上面提到的“一只老鼠走迷宫”。设num是到达的砖块数量，算法的过程描述如下：
（1）在初始位置令num=1，标记这个位置已经走过
（2）左上右下4个方向，按顺时针顺序选一个能走的方向，走一步。
（3）在新的位置num++，标记这个位置已经走过
（4）继续前进，如果无路可走，回退到上一步，换个方向再走。
（5）继续以上过程，直到结束。
在以上的过程中，能够访问到所有合法的砖块，并且每个砖块只访问一次，不会重复访问（回退不算重复），如图所示。
在这个过程中，最重要的特点是在一个位置只要有路，就一直走到最深处，直到无路可走，再退回一步，看在上一步的位置能不能换个方向继续往下走。这样就遍历了所有可能走到的位置。
这个思路就是深度搜索。从初始状态出发，下一步可能有多种状态；选其中一个状态深入，到达新的状态；直到无法继续深入，回退到前一步，转移到其他状态，然后再深入下去。最后，遍历完所有可以到达的状态，并得到最终的解。
上述过程用DFS实现是最简单的，代码比BFS短很多。
代码实现：
#include <bits/stdc++.h>
using namespace std;
char room[23][23];
int dir[4][2]={
{-1,0},//向左，左上角的坐标是（0，0）
{0,-1},//向上
{1,0},//向右
{0,1}//向下
};
int Wx,Hy,num;//WX行,Hy列用num统计可走的位置有多少
#define CHECK(x,y) (x<Wx && x>=0 && y<Hy && y>=0)//是否在room中
struct node{
int x,y;
};
void DFS(int dx,int dy){
room[dx][dy]='#';//标记这个位置，表示已经走过
num++;
for(int i=0;i<4;i++){//按左上右下四个方向顺时针深搜
int newx=dx+dir[i][0];
int newy=dy+dir[i][1];
if(CHECK(newx,newy) && room[newx][newy]=='.'){
DFS(newx,newy);
}
}
}
int main(){
int x,y,dx,dy;
while(cin>>Wx>>Hy){//Wx行 Hy列
if(Wx==0 && Hy==0){//结束
break;
}
for(y=0;y<Hy;y++){//有Hy列
for(x=0;x<Wx;x++){//一次读入一行
cin>>room[x][y];
if(room[x][y]=='@'){//读入起点
dx=x;
dy=y;
}
}
}
num=0;
DFS(dx,dy);
cout<<num<<endl;
}
return 0;
}
自己写的leetcode上面的简单题：
Leetcode100.相同的树
/**
执行结果：通过
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36 MB, 在所有 Java 提交中击败了11.36%的用户
通过测试用例：60 / 60
**/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null) return true;
if(p==null || q==null) return false;
if(p.val!=q.val) return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
Leetcode101.对称二叉树
/**
执行结果：通过
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.5 MB, 在所有 Java 提交中击败了38.38%的用户
通过测试用例：197 / 197
**/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSame(root,root);
}
public boolean isSame(TreeNode t1,TreeNode t2){
if(t1==null && t2==null){
return true;
}
if(t1==null || t2==null){
return false;
}
return t1.val==t2.val && isSame(t1.left,t2.right) && isSame(t1.right,t2.left);
}
}
Leetcode104.二叉树的最大深度
/**
执行结果：通过
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了31.93%的用户
通过测试用例：39 / 39
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
Leetcode111.二叉树的最小深度
/**
执行结果：通过
执行用时：5 ms, 在所有 Java 提交中击败了69.23%的用户
内存消耗：59 MB, 在所有 Java 提交中击败了11.52%的用户
通过测试用例：52 / 52
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
if(root.left==null && root.right==null){
return 1;
}
int min=Integer.MAX_VALUE;
if(root.left!=null){
min=Math.min(minDepth(root.left),min);
}
if(root.right!=null){
min=Math.min(minDepth(root.right),min);
}
return min+1;
}
}
DFS和BFS是算法设计中的基本技术,是基础的基础。
这两种算法都能遍历搜索树的所有结点,区别在于如何扩展下一个结点。DFS扩展子结占的子结点，搜索路径越来越深,适合采用栈这种数据结构,并用递归算法来实现:BFS扩展子结点的兄弟结点,搜索路径越来越宽,适合用队列来实现。
1.复杂度
DFS和 BFS对所有的点和边做了一次遍历,即对每个结点均做一次且仅做一次访问设点的数量是V,连接点的边总数是E,那么总复杂度是O(V＋E),看起来复杂度并不高但是,有些问题的V和E本身就是指数级的,例如八数码问题的状态,是O(n!)的。因此在搜索时需要用到剪枝、回溯、双向广搜、迭代加深、A *、IDA *等方法,尽量减少搜索的范围,使访问的总次数远远小于O(V+E)。
2．应用场合
DFS一般用递归实现,代码比BFS更短。如果题目能用DFS解决,可以优先使用它。当然,一些问题更适合用 DFS,另一些问题更适合用 BFS。在一般情况下,BFS是求解最优解的较好方法,例如像迷宫这样的求最短路企回题应以用 BFS。而DFS多用于求可行解。