1、深度优先搜索DFS

不管哪条路一定要走到头，然后再往回走，往回退一步之后看看还有没有没走过的路，如果有，那么就继续对没走过的路进行DFS，如果没有就再退一步。

算法思路奇怪或者对空间要求较高用DFS。

DFS俗称暴力搜索，最重要的就是把他的顺序想明白。用一个什么样的顺序去遍历所有方案。BFS搜索流程是一个树，如果想不明白就画一个树就想明白了。

两个操作：

• 回溯
• 剪枝

1.1 DFS例题：数字全排列

1.2 数字全排列解答

首先需要去考虑搜索的顺序：

就是有3个坑位，我们每一次只能填一个数字，后续就不能跟前面的一样了

注意：回溯需要恢复现场，下去时什么样子，回来时也要恢复成什么样子。

#include<iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; 
bool st[N]; // 判断这个点是否被用过了

void dfs(int u)
{
    if(u == n) // 边界
    {
        for(int i = 0; i < n; i++) cout << path[i] << " ";
        puts("");
        return;
    }

    // 依次枚举每个分支，即当前位置可以放哪些数
    for(int i = 1; i <= n; i++)
        if(!st[i]) // 也可以不开bool数组而采用移位操作
        {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            // 恢复现场
            path[u] = 0; // 这步可以省略，因为每次path[u]会被覆盖
            st[i] = false;
        }
}
int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

1.3 DFS例题：n皇后问题

1.4 n皇后问题解答

• 思路一：

跟我们搜索全排列是一样的，搜索顺序为：从第1行开始看，我们的皇后可以放在哪一列，枚举每一行这个皇后放在哪个位置。

如下图所示：可以得出：对角线的个数是2n-1个。所以N要开20

每一行去遍历，那么在遍历的过程中，只要去判定列和正反对角线是否满足条件就可以了。

而正反对角线只需要用他与y轴的截距来表示就可以了。原因如下：

正对角线：y = x + b， 反对角线：y = -x + b。

那么正对角线：b = y - x，因为他有可能为负数，我们需要将他变为正数，给他加一个偏移量n据可以了，如上图的8*8矩阵，这样最大截距是7，7+8 = 15，最小正截距为0，0+8 = 8，最大负截距为-1，-1+8 = 7，最小付截距为-7，-7+8 = 1，彼此互不干扰。

对于反对角线：b = y + x，值全部为正数，直接存储就可以了。

对于满足条件的位置，就将棋子放置进去并且将对应的条件进行更新。

时间复杂度：最坏O(\(n \times n!\))。

#include<iostream>

using namespace std;

const int N = 20;

int n;
int path[N];
bool col[N]; // 判断这个点是否被用过了
bool dg[N],udg[N]; // 正反对角线
char g[N][N];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return;
    }
    for(int i = 0; i < n; i++)
    // (u,i)这个点在dg[u+i]这个对角线上,u+i表示的就是截距
    // 对角线实际是y=x+b,那么b=y-x,防止他是负数，给他搞个偏移量，就+n就可以了
        if(!col[i] && !dg[u+i] && !udg[n-u+i]) 
        {
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            dfs(u+1);
            // 恢复现场
            col[i] = dg[u+i] = udg[n-u+i] = false;
            g[u][i] = '.';
        }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            g[i][j] = '.';
    dfs(0);
    return 0;
}

• 思路2:一个格子一个格子枚举。

每个格子都是2个选项，放或不放，当我们枚举完最后一个格子即\(n^2\)就得到了答案。

时间复杂度：O(\(2^{n^2}\))。

#include <iostream>

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];

void dfs(int x, int y, int s)
{
    if (s > n) return;
    if (y == n) y = 0, x ++ ;

    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    g[x][y] = '.';
    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;

    dfs(0, 0, 0);

    return 0;
}

2、宽度优先搜索BFS

层层进行搜索，每一层都搜索完之后才会搜索下一层

因为每次都存储一层，在每条边权重为1的情况下第一次搜索到的点一定是最近的点，具有最短路性质

设计到最短路都可以考虑BFS。

宽搜的框架：

• 起始状态 \(\to\) queue

• while（queue不空){

  t \(\gets\) 队头（每一次取出队头元素）

  拓展t所有的邻接点x：

  ​ if（x未被遍历）：

  ​ queue \(\gets\) x，把x入队

  ​ 更新x的距离，d[x] = d[t] + 1;

2.1 BFS例题：走迷宫

2.2 走迷宫解答

迷宫的上下左右可以用向量表示：

向上：（-1，0），向下：（1，0）

向左：（0，-1），向右：（0，1）

使用了自定义的

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];

PII q[N*N];
// 如果想输出最短路径，就开个数组记录一下这个点是从哪个点来的就可以了
PII prev_road[N][N];
int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0,0};

    memset(d, -1, sizeof d);
    d[0][0] = 0;

    // 以向量的方式进行上下左右移动
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    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 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                prev_road[x][y] = t; // 记录路径
                q[++tt] = {x,y};
            }
        }
    }
    // 输出路径
    int x = n-1, y = m-1;
    while(x || y) // x和y不同时为0
    {
        cout << x << ' ' << y << endl;
        auto t = prev_road[x][y];
        x = t.first, y = t.second;
    }

    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() << endl;

    return 0;
}

3、BFS和DFS对比

	DFS	BFS
存储结构	stack	queue
空间	O(h)	O(\(2^h\))
性质：	不具有最短路性质	具有最短路性质