DFS与BFS

1.DFS与BFS

DFS：深度优先搜索（Depth-First-Search）

BFS：宽度优先搜索（Breadth-First-Search）

DFS和BFS的对比

• DFS使用栈（stack）来实现，BFS使用队列（queue）来实现

• DFS所需要的空间是树的高度h，而BFS需要的空间是2^h （DFS的空间复杂度较低）

• DFS不具有最短路的特性，BFS具有最短路的特性

BFS具有最短路的特性：当前每条边的权重相等时，BFS遍历从当前点到每个点的距离都是最短的

（一）DFS

• 回溯：回溯的时候，一定要记得恢复现场
• 剪枝：提前判断某个分支一定不合法，直接剪掉该分支

经典问题：全排列问题、n皇后问题

AcWing 842.排列数字

**实现思路：**利用深度优先搜索

• 每次搜索确定一个位置的数字，然后回溯判断是否有其它可能，回溯后要恢复现场
• 设置一个结果数组path[]，存储每次确定放置的数字。dfs递归参数设置为u，表示要判断的第几个数字，若un表示找到一个序列输出，然后回溯（注意u从0开始，un时就意味着已经放置好了n个数）。
  • 设置一个bool数组st[]，st[i]=true表示数字i已经放置，否则未放置
  • 若未放置，则将i放置在当前位置path[u]，且设置对应数组st[i]=true
  • 然后递归到下一个为止dfs(u+1)，继续判断放置
  • 到达最后一个位置输出一次结果后，回溯，恢复现场，设置st[i]=false，然后继续循环判断这个位置放另一个数

#include <iostream>
using namespace std;
const int N=7;
int n;
int path[N],//path存储结果(从0开始)
bool st[N];//st表示当前数字是否已使用(放置)(从1开始) 初始化默认为false
 
//深度优先搜索
void dfs(int u){//u表示当前处理第几个数 总共三个 0 1 2... u=n时已处理n个
    if(u==n){//已找到一个结果
        for(int i=0;i<n;i++) cout<<path[i]<<" ";
        cout<<endl;
        return ;
    }
    //否则继续搜索
    for(int i=1;i<=n;i++){
        if(!st[i]){//当前数字未被使用
            path[u]=i;//使用
            st[i]=true;
            dfs(u+1);//递归
            st[i]=false;//回溯后要恢复现场
        }
    }
    
}
 
int mian(){
    cin>>n;
    dfs(0);//从0开始
    return 0;
}
 
 
 

AcWing 843.n-皇后问题

方法一：按行枚举，dfs(u)

• 确定n个位置，每次需要回溯和剪枝(即发现条件不符合时直接跳过这种情形，而不是把这种情况完成再进行排除，从而减少了时间复杂度操作。

• 条件判断包括行、列、主对角线、副对角线。u表示目前放置第几个皇后，也表示第几行。用列i作为循环条件，每次确定一行中某个位置(u，i)放置皇后

  • 对于行：由于每行只有一个皇后，要放置n个皇后，每次递归处理一行，放置一个皇后，当u==n时，结束表示放置完毕，即行为隐藏编号，无需额外的行数组

  • 对于列：设置一个列数组col[]，bool型，col[i]为true时表示当前列i已有皇后

  • 对于主对角线：同样设置一个bool数组dg[]，dg[u+i]为true时表示当前位置的主对角线方向有皇后

  • 对于副对角线：设置一个bool数组udg[]，udg[i-u+n]为true时表示当前位置的副对角线方向有皇后

    关于为什么是u+i，i-u+n：如果将棋盘类比成平面直角坐标系，左上角的点就是坐标原点O。可以把u看作横坐标，i看作纵坐标，若主对角线v1是不通过O的，那么v1上的点的横纵坐标之和不变，即u+i不变，副对角线v2上的点的横纵坐标只差不变即i-u不变，但是r-i会小于0（最小为0-8==-8），由于数组下标的限制，所以要对i-u加8。(如下图)

• 注意每次回溯前，即放置皇后后，要设置当前列、主对角、副对角为true；回溯后要设置当前列、主对角、副对角为false（即回到当前位置要恢复现场）

#include <iostream>
using namespace std;
const int N=20;
char g[N][N];//存储棋盘
bool col[N],dg[N],udg[N];
int n;
 
//深度优先搜索
void dfs(int u){//u表示行，从1开始
    if(u==n){//表示棋盘已经遍历完 皇后已经放好 输出一次结果
        for(int i=0;i<n;i++) puts(g[i]);//使用puts直接按行输出
        cout<<endl;
        return ;
    }
    //继续处理
    for(int i=0;i<n;i++){//按列循环处理
        if(!col[i] && !dg[u+i] && !udg[u-i+n]){//当前位置(u,i)可以放皇后
            g[u][i]='Q';//放置皇后
            col[i]=dg[u+i]=udg[u-i+n]=true;//更新标志
            dfs(u+1);//继续递归一行
            col[i]=dg[u+i]=udg[u-i+n]=false;//回溯后 恢复现场
            g[u][i]='.';
        }
    }
}
 
int mian(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';//初始化棋盘
    dfs(0);//从0开始，表示第一行
    return 0;
}
 

方法二：将参数设置为更易于理解的三个参数，即行号、列号、皇后放置数量，dfs(x,y,s)

• 设置四个数组，行数组row[]，列数组col[]，主对角数组dg[]，副对角数组udg[]，分别表示当前位置的四个方位是否有皇后

• 从第一行第一列(0,0,0)开始，每次首先判断当前行是否走完，走完就移动到下一行的第一列继续

  • 然后判断是否走到最后一行，若走到最后一行，则判断皇后是否放完，若放完就输出结果，结束

• 对于当前位置(x,y)有两种选择，不放皇后和放皇后；

  • 不放皇后，直接递归到下一列dfs(x,y+1,s)；
  • 放皇后。进行判断当前位置(x,y)的四个方位是否符合条件。若符合则放置皇后，更新四个数组为true，然后继续向下寻找下一个放置皇后的位置，然后回溯，恢复四个数组为false(恢复现场)

#include <iostream>
using namespace std;
const int N=20;
char g[N][N];
bool row[N],col[N],dg[N],dg[N];//增加一个row数组，记录当前行中是否已有皇后
int n;
 
//(x,y)坐标，s表示当前已放皇后数 均从0开始
void dfs(int x,int y,int s){
    if(y==n){x++;y=0;}//已经处理完一行 处理下一行
    if(x==n){//已处理完所有行
        if(s==n){//可能顺序遍历完后 皇后没有完全放好即s<=n
			//若皇后都放好了 输出结果
            for (int i = 0; i < n; i++) puts(g[i]);
            cout << endl;
        }
        return;
    }
    
    //行还未处理完 继续处理 两种情况
    //当前位置不放皇后
    dfs(x,y+1,s);//向下一列继续
    
    //当前位置放皇后 
    if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]){//若可放
        g[x][y]='Q';
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;//更新标记
        dfs(x,y+1,s+1);//这里可不可以直接x+1?..
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;//恢复现场
        g[x][y]='.';
    }
    
}
 
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';//初始化棋盘
    dfs(0,0,0);
    return 0;
}

（二）BFS

一般通过队列实现，当边的权值相同时具有最短性，可以求最少操作步数.相比DFS无需回溯，而是逐层搜索。

AcWing 844.走迷宫

**实现思路：**广度优先搜索

• 设置一个二维数组g[][]存储图。设置一个队列q[]（pair[int][int]类型的，每个值存储坐标(x,y)），表示当前到达的坐标位置。设置一个距离数组d[][]，d[x][y]表示到原点的距离
• 当队列不为空时，取出队头元素，向四个方位进行判断，看是否可走，可走的路径更新距离，坐标再存入数组
  • 关于方位的选择，为简化代码，不用写四行判断来检验每个方位。设置两个一维数组dx[4]，dy[4]分别存储{0,1,0,-1}、{1,0,,-1,0}，然后循环四次，每次坐标加上对应的dx、dy，判断当前位置是否可走，若可走就更新坐标到原点的距离d[x][y]+1，并将新坐标加入队列

#include <iostream>
#include <cstring>
using namespace std;
const int N=10;
typedef pair<int><int> II;//用来表示队列存储的元素 即坐标(x,y)
int g[N][N],d[N][N];//图 距离数组表示(x,y)到原点的距离
II q[N*N];//队列  这里用数组模拟队列
int n,m;
 
//返回最终结果
int bfs(){
    memset(d,-1,sizeof d);//初始化距离数组为-1 表示当前坐标还未走过
    d[0][0]=0;
    q[0]={0,0};//队列初始化，从原点(0,0)开始
    int hh=0，tt=0;//队头、队尾指针
    int dx[4]={0,1,0,-1},dy={1,0,-1,0};//用来形成四个方位 简化代码
    while(hh<=tt){//队列不为空时
        auto t=q[hh++];//取出队头元素
        for(int i=0;i<4;i++){//四个方位循环判断哪条可走
            int x=t.first+dx[i],y=t.second+dy[i];//得到新坐标
            if(x>=0 && y>=0 && x<n && y<m && g[x][y]==0 && d[x][y]==-1){//这个坐标可以走
                d[x][y]=d[t.first][t.second]+1;//更新距离+1
                q[tt++]={x,y};//当前坐标入队
            }
        }
    }
    return d[n-1][m-1];//返回终点到原点的距离 即为结果
}
 
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    cout<<bfs[];
    return 0;
}

补充：存储经过路径

设置一个二维数组p[][](pair<int><int>型)，p[x][y]存储当前位置坐标的前驱坐标，判断好要走的方位时，更新

然后从(n-1,m-1)开始遍历输出，即为从终点到原点经过坐标（也就是逆序输出）

II p[N][N];
p[0][0]={-1,-1};
if(x>=0 && y>=0 && x<n && y<m && g[x][y]==0 && d[x][y]==-1){
                d[x][y]=d[t.first][t.second]+1;
                q[tt++]={x,y};
    			p[x][y]=t;//记录当前坐标的前驱坐标 即从哪个点过来的
            }
//输出
int x=n-1,y=m-1;//终点到原点的路径输出
while(x>=0 && y>=0){
    cout<<x<<","<<y<<endl;
    auto t=p[x][y];//得到前驱
    x=t.first,y=t.second;
}

AcWing 845. 八数码

实现思路：

• 首先题意：

• 可以转化为求图的最短距离，且权值为1，使用BFS

• **怎么表示状态（即每次移动后的矩阵是怎样的）？**显然用邻接矩阵、邻接表都不好

  • 将3x3的矩阵按顺序转化为字符串，即s=“123x46758”
  • BFS要使用队列，这时队列就存储字符串queue<string>

• 如何记录到达每一个状态时已经移动的距离？

  • 使用一个字典，字符串状态与已经移动的距离相对应，即unordered_map<string,int>

• 然后按照BFS的步骤进行。

注：

• 字符串下标k—⇒矩阵位置(x,y)：x=k/3,y=k%3
• 矩阵位置(x,y)—⇒字符串下标k：k=x*3+y

其他理解：

AcWing 845. 八数码 - AcWing

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
 
//找到字符串转移到目标状态的最少交次数
int bfs(string start){
    //定义目标状态
    string end="12345678x";
    //定义字符串队列  
    queue<string> q;
    q.push(start);//初始状态入队
    //定义距离数组
    unordered_map<string,int> d;//用SLT中的unordered_map
    d[start]=0;//初始状态距离为0
    
    //四个方向的转移
    int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
    
    while(q.size()){//只要队列不为空
        auto t=q.front();//得到队头元素
        int dist=d[t];//得到当前已转移的距离
        
        if(t==end) return dist;//如果现在已经转移到最终状态 退出
        
        //得到当前状态中x的位置 再转化为对应矩阵中的位置
        int k=t.find('x');//使用string中自带的find函数
        int x=k/3,y=k%3;
        
        //遍历四个可移动的方向
        for(int i=0;i<4;i++){
            //转移后的坐标
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && a<3 && b>=0 && b<3){//可以转移过去 没有越界
                swap(t[k],t[a*3+b]);//将x和可转移位置的字符交换位置
                //如果当前状态是第一次转移 记录到队列和距离数组
                if(!d.count(t)){
                    d[t]=dist+1;
                    q.push(t);
                }
                //还原状态 为另一个可转移方向做准备
                swap(t[k],t[a*3+b]);
            }
        }
        
    }
    //始终达不到目标状态 返回-1
    return -1;
}
 
int main(){
    string start;
    for(int i=0;i<9;i++){
        char c;
        cin>>c;
        start+=c;
    }
    cout<<bfs(start);
    return 0;
}