dfs + bfs 几类经典板子

---

策略性的dfs

前言

dfs通常都是搭配着回溯算法一起使用的，求解的问题一般是多个状态且对应多决策的，将这些状态看成是树的结点，

根结点是初态， dfs从根结点开始一层一层地往下探索(子结点)，并将经过的结点存储在path中，当到了叶子结点时表示已找到问题的解，

此时将path添加至结果集合中；然后回退到上一个结点，上一个结点又接着探索它的其它子结点，如果没有接着回退，这就是回溯。

基本的算法板子如下：

dfs:

 if 满足条件:
    添加到结果集合或者是print
    return
 for elem in 可选的状态集合：
    覆盖选中的状态
    dfs(下一层)
    撤销选中的状态
1
2
3
4
5
6
7
8
9

---

1. 排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1≤n≤7
输入样例：

3
1

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1
2
3
4
5
6

---

利用state[i]表示数字i是否已在排列内，path[]来存储排列中的一种，deep既是深度也是path的长度。

C++代码

#include 
#include 
using namespace std;

int n;
int path[10];       //排列的结果
int state[10];      //存数字i的状态，是否在排列内

void dfs(int deep){
    if(deep > n){      //到底了
        for(int i = 1;i <= n;i ++)      cout << path[i] << " ";
        cout << endl;
        return;
    }
    for(int i = 1;i <= n;i ++){
        if(!state[i]){
            path[deep] = i;
            state[i] = true;
            dfs(deep + 1);      //接着向下探索
            state[i] = false;
        }
    }
}

int main(){
    cin >> n;
    memset(state, false, sizeof(state));
    dfs(1);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

2. n-皇后

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9

输入样例：

4
1

输出样例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
1
2
3
4
5
6
7
8
9

---

C++代码(超时了)

一开始考虑的是将图中几个条件约束均用数组表示出来，即用row[10], col[10], diag[20], udiag[20]来分别表示行、列、斜线、反斜线上皇后的状态，然后dfs两层循环行上坐标i和列上坐标j然后检查条件，注意要让让i从start开始遍历，这样整个dfs过程保证了是一行一行地向下放置皇后，找到解后再一行一行地向上回溯。可惜这样做超时了，前面的样例都能通过Orz Orz。

#include 
#include 
#include 
using namespace std;

/**
 * @brief 棋盘从上到下(1~n)、从左到右(1~n)
 * 正斜线：左上到右下，同一斜线元素满足“= x - y + n”(n是个偏移值，防止传入的下标为负)
 * 反斜线：右上到左下，同一斜线元素满足“= x + y”
 */

int n;
char g[10][10];
bool row[10], col[10], diag[20], udiag[20];     //行、列、斜线、反斜线上皇后的状态

void dfs(int start, int deep){
    if(deep == n){
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= n;j ++)
                printf("%c", g[i][j]);
            printf("\n");
        }
        printf("\n");
        return;
    }

    for(int i = start;i <= n;i ++){
        if(row[i])      continue;
        for(int j = 1;j <= n;j ++){
            if(col[j])      continue;
            if(!row[i] && !col[j] && !diag[i - j + n] && !udiag[i + j]){
                g[i][j] = 'Q';
                row[i] = col[j] = diag[i - j + n] = udiag[i + j] = true;

                dfs(start + 1, deep + 1);

                row[i] = col[j] = diag[i - j + n] = udiag[i + j] = false;
                g[i][j] = '.';
            }
        }
    }
}


int main(){
    memset(g, '.', sizeof(g));
    
    cin >> n;
    dfs(1, 0);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

---

C++代码(AC)

通过观察发现，深度deep的进度和行或列的进度是一致的（相差1），那么可以去掉一层循环而将“列数”体现在深度上：

j = deep + 1，这样就大大减去了时间，具体再看注释。

#include 
#include 
#include 
using namespace std;

/**
 * @brief 棋盘从上到下(1~n)、从左到右(1~n)
 * 降维，撤去“表示列上皇后”的数组，将列数体现在dfs的深度deep上，也即j等于deep + 1(deep从0开始，j从1开始)
 * dfs的过程有所变化，是一列一列地向右放置皇后，找到解后一列一列地向左回溯
 * 
 * 正反斜线上的元素规律不变
 */

int n;
char g[10][10];
bool row[10], diag[20], udiag[20];     //行、斜线、反斜线上皇后的状态

void dfs(int deep){
    if(deep == n){
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= n;j ++)
                printf("%c", g[i][j]);
            printf("\n");
        }
        printf("\n");
        return;
    }
    
    int j = deep + 1;
    for(int i = 1;i <= n;i ++){
        if(!row[i] && !diag[i - j + n] && !udiag[i + j]){
            g[i][j] = 'Q';
            row[i] = diag[i - j + n] = udiag[i + j] = true;

            dfs(deep + 1);

            row[i] = diag[i - j + n] = udiag[i + j] = false;
            g[i][j] = '.';
        }
    }
}

int main(){
    memset(g, '.', sizeof(g));
    
    cin >> n;
    dfs(0);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

---

策略性的bfs

前言

bfs与其说是宽搜不如说是决策树的层序遍历，因为在决策树中叶子结点对应的是该问题的一个可行解，而bfs通常要解决的是求问题的最短路径解，就说明要求的解对应的叶子结点距离根结点要尽量的近。

如下图的树所示，虽有两个叶子结点决策7和9，但结点7距离起点更近，所以它才是要找到“最短路径解”，为了较快地找到这个结点，使用层序遍历，也即bfs。

---

bfs和dfs算法的最大的区别是bfs不是递归算法，仅需要借助一个队列q，存入结点后又不断扩展结点就完成了整个遍历。

算法的通用板子是：

bfs:

 q.push(起点)
 while (q不空):
   t = 取出队头
   
   for tt in t的下一步决策集合:
     if (tt满足要求 且 没走过):
       tt 打上已走过的标记
       tt 加入队列
1
2
3
4
5
6
7
8
9
10

---

3. 走迷宫

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤100

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
1
2
3
4
5
6

输出样例：

8
1

---

直接套上模板就可以做，注意dist数组的初始化为-1，dist的作用除了记录距离还有表示dist[i][j]是否已经遍历过(为-1)。

C++代码

#include 
#include 
#include 
using namespace std;
typedef pair<int, int> pii;

const int N = 110;

int n, m, x, y;
int g[N][N], dist[N][N];        //图、各点到(1,1)的距离
int dx[4] = {1, 0, 0, -1}, dy[4] = {0, 1, -1, 0};           //移动方向
queue<pii> q;

bool check(int a, int b){
    return a >= 1 && a <= n && b >= 1 && b <= m;
}

void bfs(int a, int b){         //终点是dist[n][m]的值
    q.push({a, b});
    
    while(!q.empty()){
        pii t = q.front();
        q.pop();

        for(int i = 0;i < 4;i ++){
            x = t.first + dx[i];
            y = t.second + dy[i];

            if(check(x, y) && g[x][y] == 0 && dist[x][y] == -1){
                dist[x][y] = dist[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
}

int main(){
    ios:: sync_with_stdio(false);
    memset(dist, -1, sizeof(dist));
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> g[i][j];
    
    dist[1][1] = 0;
    
    bfs(1, 1);
    cout << dist[n][m] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---

4. 八数码

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

1 2 3
x 4 6
7 5 8
1
2
3

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x
1
2
3

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x
1
2
3

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式
输入占一行，将 3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

输入样例：

2 3 4 1 5 x 7 6 8
1

输出样例

19
1

---

样例中的变化过程看似几步轻松搞定，但bfs整个操作过程中会走很多“弯路”才会到达理想中那个解。

以下图(图片来源于百度)为例，可以清晰地看到整个算法的流程：

---

这题也是几乎套模板就可以做，但不同之处是要对图上进行改动，而较简便地表示并可修改整个图成了一个难点。

其实只需要将棋盘的状态转换为一维的字符串，而不用真正地存二维的字符矩阵，只是在搜索下一个状态，以及进行数字交换时要进行一维的下标与数字在二维空间下的坐标互相转换，它们的对应关系有：

1—>2
x = index / 3
y = index % 3
2—>1
index = 3 * x + y

然后将每个棋盘状态与其跟初始棋盘相差的步数存入HashMap中，最终输出哈希表中的"12345678x"的值即是答案，如果哈希表中不存在这个字符串，说明没找到解，输出-1即可。

Java代码

import java.util.*;

public class Main {
    private static String start = "";
    //将已探索到的棋盘状态存入map，value是从初始棋盘移动到此的步数
    private static HashMap<String, Integer> map = new HashMap<>();
    private static String goal = "12345678x";
    private static Queue<String> q = new LinkedList<>();
    private static int[] dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
    private static int locx;		//"x"在字符串中的下标

    public static boolean check(int a, int b) {
        return a >= 0 && a <= 2 && b >= 0 && b <= 2;
    }

    public static String swap(String t, int a, int b){		//返回交换后的棋盘
        char[] s = t.toCharArray();
        s[locx] = s[a * 3 + b];     //a * 3 + b: 二维转一维
        s[a * 3 + b] = 'x';
        return new String(s);
    }

    public static void bfs(){
        q.add(start);
        while(!q.isEmpty()){
            String t = q.poll();
            if (t.equals(goal))     //找到解的结点
                return;

            int dist = map.get(t);
            locx = t.indexOf("x");
//            x: locx / 3;      一维转二维
//            y: locx % 3;

            for (int i = 0; i < 4; i++) {
                int x = locx / 3 + dx[i], y = locx % 3 + dy[i];
                if (check(x, y)){
                    String tt = swap(t, x, y);
                    if(!map.containsKey(tt)) {		//已走过标记
                        map.put(tt, dist + 1);
                        q.add(tt);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i = 1;i <= 9;i ++)
            start += in.next();
        in.close();
        map.put(start, 0);

        bfs();
        System.out.println(map.containsKey(goal) ? map.get(goal) : -1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

---

其实可以发现，用dfs或bfs解决问题最关键的就是 “会模拟”，也即能抽象出每个决策的状态表示、找到空间复杂度小的存储方式。

---

树上的dfs

前言

从这里开始，后面两项介绍的关于树或图的遍历均采用邻接表的存储方式，再确切一点，是一种叫做链式前向星的数据结构。
这里只会用到它的一个操作——构造两个点之间的一条边。即

void add(int a, int b){		//邻接表的头插法，b -> a
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
1
2
3
4
5

那么dfs的模板也会有所变化，会更简洁：

dfs(int x){		//结点编号为x
	st[x] = true;		//访问过x了
	for(int i = h[x];i != -1;i = ne[i]){		//遍历子结点的方式
		int j = e[i];		//x的邻接点j，其实也都是它的子结点
		if(!st[j]){
			dfs(j)
			...
		}
	}
	...
}
1
2
3
4
5
6
7
8
9
10
11

树的重心

给定一颗树，树中包含 $n$ 个结点（编号 1∼$n$）和 $n$ −1条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤ $n$ ≤$10^5$

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
1
2
3
4
5
6
7
8
9

输出样例：

4
1

---

为了找到这棵树的“重心”，可以先对每个点试探，看能否满足题给要求，定义一个res表示剩余各个连通块中点数点最大值，然后每次对res进行max迭代即可得出结果。

注意这里对每个点的试探并不是真的会将它删除而后看结果，而是间接地计算出题目要求的数据。

以下图中所示的树为例，假设要删除红圈中的结点。

那么其实将它删除后还剩的连通块就如下图中棕色圈住的两块所示：

而如何得到这两块中的点个数呢？

可以发现下面的连通块的大小就是这个结点的所有子树点数和，假设为sum，因此可以递归地调用dfs，对所有子结点使用，深搜每个子树直至叶子结点：dfs每次要返回一个值，该值就是调用了该dfs的结点的子树点数和，一只递归地往下执行，直至叶子结点返回 1。

然后每次dfs完返回到最开始调用它的父结点处时，要对各个子树（连通块）进行一个大小的比较，把点个数最大的值存到max_size里。

再观察图可以发现，“待删除”结点的下面连通块点数值有了，而上边连通块的值其实也就出来了，
它就恰好等于n - sum - 1，其中$n$为结点总个数，-1是因为还要把自己给减掉，最后再跟max_size进行一次比较，然后维护一下res即：res = min(res, max_size)。

具体还可参考代码注释。

C++代码

#include 
#include 
#include 
using namespace std;

const int N = 10e5 + 10, M = 2 * N;

int e[M], ne[M], h[N], idx = 0;
bool st[N];
int res = N, n;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int dfs(int x){         //返回点x与它所有子树构成的连通块 的 点的个数
    st[x] = true;
    int sum = 0;        //子树的点的个数总和（不知道还有没子树，所以先定为0）
    int max_size = -1;       //以"x为重心"时的最大连通块的大小

    for(int i = h[x];i != -1;i = ne[i]){
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);         //往下搜索

            max_size = max(max_size, s);        //子树里筛max
            sum += s;
        }
    }
    max_size = max(max_size, n - 1 - sum);      //跟点x头上那个连通块筛一下max

    res = min(res, max_size);       //维护res

    return sum + 1;         //返回给父结点
    //x是叶子结点时：return 0 + 1

}

int main(){
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0;i < n;i ++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);      //树——特殊的无向图
    }

    dfs(1);

    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

---

图上的bfs

前言

在这里，bfs的模板相较之前改动很小，仍然是使用队列存储每个结点的状态然后一层一层地扩展。

图中点的层次

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1 ，点的编号为 1∼$n$。

请你求出 1 号点到 $n$ 号点的最短距离，如果从 1 号点无法走到 $n$ 号点，输出 −1。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围

1≤$n$,$m$≤$10^5$

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4
1
2
3
4
5
6

输出样例：

1
1

---

首先，从结点编号1开始逐层地向外扩展，那么再定义一个dist[]数组表示与根结点的距离，由于从1开始的，所以dist[i]就表示了i到1之间的距离。

dist会初始化所有值为-1，而这个-1可以作为某个结点i是否已被访问过的标记，即if(dist[i] == -1)。

因此再套用bfs的模板，一圈一圈地向外扩展，如果与结点n是可达的，计算距离后直接输出就可以了，而不可达的话就输出dist[n]的默认值-1。

C++代码

#include 
#include 
#include 
#include 
using namespace std;

const int N = 10E5 + 10, M = 2 * N;

int n, m;
int e[M], ne[M], h[N], idx = 0;
int dist[N];
queue<int> q;       //队列存的是结点编号

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int bfs(){
    //dist初始化为-1，-1可以作为图上的扩展标记，如果n点没被访问到，说明没连通，顺而输出-1
    memset(dist, -1, sizeof dist);      

    dist[1] = 0;
    q.push(1);

    while(q.size()){
        int t = q.front();
        q.pop();

        for(int i = h[t];i != -1;i = ne[i]){
            int j = e[i];
            if(dist[j] == -1){
                dist[j] = dist[t] + 1;
                if(j == n)
                    break;      //拓展到n点，提前结束宽搜
                q.push(j);
            }
        }
    }

    return dist[n];
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;

    while(m --){
        int a, b;
        cin >> a >> b;
        add(a, b);      //有向图
    }

    cout << bfs() << endl;
    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

值得一提的是，上述的邻接表存储以及相关搜索的模板不论是在树或是在图上均合适。