深度优先搜索（DFS）和广度优先搜索（BFS）是两种搜索树和图的基本策略。其搜索的思想所引申来的题目也比较多，需要引起足够的重视
深度优先搜索DFS
深度优先搜索它是从某个状态开始，不断地转移状态直到无法转移（一层一层往下搜），然后回退到前一步状态，继续转移到其他状态，如此不断重复，直至找到最终的解。
邻接矩阵存储图的DFS遍历
- 节点编号为 1 ~ n
const int INF = 0x3f3f3f3f;
// 邻接矩阵存储图的信息g[i][j]表示顶点 i 到顶点 j 这条边的权值大小
int g[N][N];
bool st[N];
// 初始化
memset(g, 0x3f, sizeof g);
void dfs(int u) {
// 先标记这个点已经被访问过
st[u] = true;
// 递归地去遍历和该点连通的点
for (int i = 1; i <= n; i++) {
if (!st[i] && g[u][i] != INF)
dfs(i);
}
}
邻接表存储图的DFS遍历
- 节点编号为 1 ~ n
// 使用邻接表来存储图
vector<int> g[N];
bool st[N];
void dfs(int u) {
// st[u] 表示点u已经被遍历过
st[u] = true;
// 递归地去遍历和该点连通的点
for (int i = 0; i < g[u].size(); i++) {
if (!st[g[u][i]])
dfs(g[u][i]);
}
}
树的重心
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数n，表示树的结点数。接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。
输出格式
输出一个整数m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
- DFS遍历每个结点，记录以每个结点为根的子树中点的数量，不断更新，找到子树连通块中最大数的连通块
- 该结点上面一共 个结点，再取最大值
- 找到该最大值最小的那一种情况
#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;
vector<int> g[N];
bool st[N];
int ans = N;
int n;
// 以u为根的子树中点的数量
int dfs(int u) {
st[u] = true;
// sum记录子树中所有连通块的结点数量
int sum = 1;
// 记录将该点删掉之后，子树中连通块的最大值
int size = 0;
for (int i = 0; i < g[u].size(); i++) {
int j = g[u][i];
if (!st[j]) {
// 记录当前子树的结点
int s = dfs(j);
size = max(size, s);
sum += s;
}
}
// 和非子树的连通块的结点数比较，取最大结点数
size = max(size, n - sum);
// 答案取最小的一种情况
ans = min(ans, size);
return sum;
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1);
cout << ans << endl;
return 0;
}
枚举排列
给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
这其实是一种DFS搜索的思想，我们构造一颗搜索树：
在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。「路径」和「选择」是每个节点的属性，函数在树上游走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：撤销选择，恢复现场，即为回溯
#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] << ' ';
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 main() {
cin >> n;
dfs(0);
return 0;
}
n - 皇后问题
n-皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数n。
输出格式
每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
- 相当于是枚举每一行的皇后放在哪一列
- 只是多了规则，很多不合理的方案可以提前结束搜索，这就是所谓需要进行剪枝
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
/**
* 检查第i行和第j列能否放置
**/
bool isValid(int x, int y) {
// 检查第y列上是否有冲突
for (int i = 0; i < n; i++) {
if (g[i][y] == 'Q')
return false;
}
// 检查右上方是否有皇后冲突（因为我们逐层放，只用考虑斜上方的情形）
for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) {
if (g[i][j] == 'Q')
return false;
}
// 检查左上方是否有皇后冲突
for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
if (g[i][j] == 'Q')
return false;
}
return true;
}
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++) {
// 这里相当于进行剪枝操作
if (!isValid(u, i))
continue;
// 选择
g[u][i] = 'Q';
dfs(u + 1);
// 撤销选择
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;
}
广度优先搜索 BFS
- 广度优先搜索（BFS）与深度优先搜索不同在于搜索的顺序，广度优先搜索总是先搜索距离初始状态近的状态。一层一层往下搜索，使用队列。（开始状态 --> 只需要1次就可以到达的所有状态 --> ......）对于同一个状态，广度优先搜索只经过一次，因此时间复杂度为O(状态数×转移方式)
- 广度优先搜索可以找到最短路
邻接矩阵存储图的BFS遍历
- 节点编号为 1 ~ n
const int INF = 0x3f3f3f3f;
// 邻接矩阵存储图的信息g[i][j]表示顶点 i 到顶点 j 这条边的权值大小
int g[N][N];
bool st[N];
// 初始化
memset(g, 0x3f, sizeof g);
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (!st[i] && g[t][i] != INF) {
st[i] = true; // 表示点i已经被遍历过
q.push(i);
}
}
}
邻接表存储图的BFS遍历
- 节点编号为 1 ~ n
vector<int> g[N];
queue<int> q;
bool st[N];
// 初始化
st[1] = true;
q.push(1);
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = 0; i < g[t].size(); i++) {
int j = g[t][i];
if (!st[j]) {
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
图中点的层次
给定一个n个点m条边的有向图，图中可能存在重边和自环。所有边的长度都是1，点的编号为1~n。请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。
输入格式
第一行包含两个整数n和m。接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
数据范围
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1
- 我们使用BFS遍历，每一次队列取出元素：更新距离，最后输出
#include <iostream>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
vector<int> g[N];
int d[N];
int bfs() {
memset(d, -1, sizeof d);
queue<int> q;
d[1] = 0;
q.push(1);
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = 0; i < g[t].size(); i++) {
int j = g[t][i];
// 如果这个点没有遍历到，更新距离
if (d[j] == -1) {
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
cout << bfs() << endl;
return 0;
}
走迷宫
给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
输入样例：
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
输出样例：
8
- 记录了搜索到所需的最少次数
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
int n, m;
int g[N][N], d[N][N];
typedef pair<int, int> PII;
int bfs() {
queue<PII> q;
memset(d, -1, sizeof d);
d[0][0] = 0;
q.push({0, 0});
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
while (!q.empty()) {
auto t = q.front();
q.pop();
// 枚举4个方向
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i];
int 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;
q.push({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() << endl;
return 0;
}
八数码
在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。例如：
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把“x”与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让“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
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将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
输出样例
19
- 求最少交换次数 ==> BFS
- 这里是的二维数组，在我们使用BFS时候状态表示就显得不方便，因此我们做一个转换：将二维转换成一维，我们使用来表示每一个状态，最终我们需要找到的状态就是
- 在搜索的过程中，一维再换回二维去更新状态并更新距离数组dist
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int bfs(string start) {
string end = "12345678x";
unordered_map<string, int> dist;
dist[start] = 0;
queue<string> q;
q.push(start);
if (start == end)
return dist[start];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (!q.empty()) {
auto t = q.front();
q.pop();
int res = dist[t];
// 如果找到了结果，直接返回
if (t == end)
return res;
int k = t.find('x');
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]);
// 如果更新后的状态是之前没有搜到过的状态，更新距离并加入到队列
if (!dist.count(t)) {
dist[t] = res + 1;
q.push(t);
}
// 恢复状态
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main() {
string start;
for (int i = 0; i < 9; i++) {
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
