day08.搜索与图论--1（bfs+dfs+拓扑）

PS： 模板可供参考DFS解题思路

//参数用来表示当前状态; //返回值是我们dfs完成之后想要获取的数据，如果不需要返回值或者通过全局变量来记录状态的话ReturnType可以为void//函数名可以换成更有意义的名字ReturnType dfs(param1,params2,...) { if(终点状态 || 非法状态 || 需要剪枝) { ... //退出前处理 return; } for(每一个当前状态相关的下一个状态) { if(该状态合法 && 该状态未被标记) {  ...; // 当前状态应该做的处理（遍历前需要的处理）(根据实际情况来判断是否需要) 标记当前状态；  dfs（）；  ...; // 当前状态应该做的处理（遍历后需要的处理）(根据实际情况来判断是否需要) (还原标记); //可选操作, 如果加上这句就是\"回溯法\"  } } } 

一、深度优先搜索（DFS）

关键： 回溯，剪枝

（1）题目：全排列问题 (AcWing 842.排列数字)

1. 定义一个数组path[N] 来保存当前的路径/模拟DFS的过程。
2. 确定输出条件：当这个数组数字填满的时候，此时把当前的排列数字输出出来。
3. 确定单层递归逻辑：当前数组位置为空，还可以填数。
4. 回溯：恢复现场

#include #include using namespace std;const int N = 10;int n;int path[N]; // 保存路径bool st[N]; //数字使用情况，true表示已使用void dfs(int u) { //u表示层数，第一层path存一个数if (u == n) { //path[0],path[1],path[2]已存入三位数，u=n=3时退出。for (int i = 0; i < n; i++)cout << path[i];cout << \" \";cout << endl;return;}for (int i = 1; i <= n; i++)if (!st[i]) { // 数字i未使用path[u] = i;st[i] = true;dfs(u + 1); //继续填充下一个数st[i] = false; // 回溯，恢复原状}}int main() {cin >> n;dfs(0);return 0;}

（2）题目： AcWing 843.n-皇后问题

关于对角线：
row表示行，col表示列。代码中坐标用（x，y）表示，x为行，y为列。
左上方向为主对角线，右上方向为副对角线。

① 思路一：原始方法

DFS按每个元素枚举 时间复杂度O(2的n2次幂)，因为每个位置都有两种情况，总共有 n^2 个位置

1. 确定参数。
2. 确定输出条件：已遍历至最后一行，且皇后已经放置完毕。则输出
3. 确定单层递归条件：① 皇后能放在这格。② 不能放，移至改行的下一个格子。

#include #include using namespace std;// 对于一个 n * n 的矩阵，通常有 2n - 1 条对角线、反对角线const int N = 20;int n;char g[N][N]; // 存储棋盘bool row[N], col[N], dg[N], udg[N]; // 行、列、对角线、反对角线void dfs(int x, int y, int s) { //xy为坐标(x,y),s为皇后放置个数if (y == n) { //当皇后在一行中出界。纵坐标最大为n-1，等于n时已经出界。y = 0; //则，转到下一行的开头x++;}if (x == n) { // 行数出界if (s == n) { // 所有皇后已经放置完毕for (int i = 0; i < n; i++) //puts输出每一行,并自动换行puts(g[i]);puts(\"\"); //打印一个空行，用于分隔不同解}return;}// ① 判断皇后能否放在这格if (!row[x] && !col[y] && !dg[x - y + n] && !udg[x+y]) {g[x][y] = \'Q\'; //放置皇后row[x] = col[y] = dg[x - y + n] = udg[x + y] = true; // 更新状态dfs(x, y + 1, s + 1); //放置皇后，并找下一层的row[x] = col[y] = dg[x - y + n] = udg[x + y] = false; //回溯，恢复现场g[x][y] = \'.\';} // ② 不放皇后,并且访问右节点dfs(x, y + 1, s);}int main() {cin >> n;for (int i = 0; i < n; i++) // n皇后棋盘范围0~n-1for (int j = 0; j < n; j++)g[i][j] = \'.\'; //初始化全部空格子dfs(0, 0, 0); //从第一行开始找return 0;}

② 思路二（剪枝法，高效）

1. 确定输出条件：最后一行的皇后放置完毕,x出界。
2. 单层递归逻辑：遍历该行的每一列，利用col，dg，udg验证合法性。

#include #include using namespace std;// 对于一个 n * n 的矩阵，通常有 2n - 1 条对角线、反对角线const int N = 20;int n;char g[N][N]; // 存储棋盘bool col[N], dg[N], udg[N]; // 列、对角线、反对角线void dfs(int x) {if (x == n) {for (int i = 0; i < n; i++)puts(g[i]);puts(\"\");return;}//按行枚举 因为每一行都需要放皇后 相当于剪枝了// 判断皇后能否放在这格for (int y = 0; y < n; y++) {if (!col[y] && !dg[x - y + n] && !udg[x + y]) {g[x][y] = \'Q\';col[y] = dg[x - y + n] = udg[x + y] = true;dfs(x + 1); // 该层放置完毕，继续下一层col[y] = dg[x - y + n] = udg[x + y] = 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); //从第一行开始找return 0;}

二、宽度优先搜索（BFS）-----最短路

可以用bfs求最短路的前提是，权值相等。

（1）题目：AcWing 844.走迷宫

• 模拟队列法

#include #include using namespace std;const int N = 110;typedef pair<int, int> PII; // 由于地图为2维，pair便于存储路径int n, m;int g[N][N]; // 存储迷宫地图int d[N][N]; // 存储当前点到起点的最短距离int prev[N][N];PII q[N * N]; // 顺应地图的二维结构，使用PII模拟队列int bfs() {// 模拟队列int hh = 0, tt = -1;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];hh++;// 检查四个方向是否合法，若合法则可走，将位置加进队列for (int i = 0; i < 4; i++) {// 移动int x = t.first + dx[i];int y = t.second + dy[i];// d[N][N]由于初始化为了-1，所以记录最短距离的同时，也起到了 标记位置访问情况的作用// 如果 坐标没有出界+方向没有撞墙+位置没被访问过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[x][y] = t; // !记录当前位置是从哪个位置（坐标）过来的q[++tt] = {x, y}; // 将 当前点 加入队列}}}//!!!输出走出迷宫的路径，（按坐标）int x = n - 1, y = m - 1; // 从 终点 倒退来路while (x || y) {  // (x,y)=(0,0)时才退出cout << x << \' \' << y << endl;auto t = prev[x][y]; // 找来路（找前驱坐标）x = t.first, y = t.second; // 分离出坐标中的 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 < n; j++)cin >> g[i][j];cout << bfs() << endl;}

• 非模拟queue

#include #include using namespace std;const int N = 110;typedef pair<int, int> PII; // pair便于存储路径int n, m;int g[N][N]; // 存储迷宫地图int d[N][N]; // 存储当前点到起点的最短距离int prev[N][N];int bfs() {queue<PII> q;q.push({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 (!q.empty()) {auto t = q.front();q.pop();// 检查四个方向是否合法，若合法则可走，将位置加进队列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; // 更新距离数组prev[x][y] = t; // !记录当前位置是从哪个位置过来的q.push({x, y}); // 将 当前点 加入队列}}}//!输出走出迷宫的路径int x = n - 1, y = m - 1; // 从终点倒退来路while (x || y) { // (x,y)=(0,0)时退出cout << x << \' \' << y << endl;auto t = prev[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 < n; j++)cin >> g[i][j];cout << bfs() << endl;return 0;}

（2）题目：AcWing 845. 八数码

三、树与图的存储

1. 树是一种特殊的图（无环连通图）。
2. 对图而言，无向图又可以表示为a—>b，b—>a均可达的有向图。
3. 换言之，只需要掌握有向图的存储即可。有向图的存储方式有两种，邻接矩阵和邻接表

• 邻接矩阵（稠密图，不存储 重边和自环）

是一个二维数组，g[a][b]存储的是a —> b的信息，若边有权重，则g[a][b]存的就是权重；若没有权重，g[a][b]存的就是一个bool值。邻接矩阵不能存储重边，只能保留1条。

• 邻接表（稀疏图，存储重边和自环）

是给每一个结点都开一个单链表，每个单链表存的就是这个点可以走到哪些点。若一个图中有n个结点，则邻接表中就有n个单链表，在前面学习单链表时，我们给head初始化为-1，现在就给h都初始化为-1。
（邻接表的形式，与哈希表的拉链法写法一样。）

#include#include#includeusing namespace std; const int N = 1e5 + 10, M = 2 * N; // 因为是有向图，所以e和ne需要开2倍的Nint h[N], e[M], ne[M], idx; // h数组存的是n个链表的 链表头 void add(int a, int b) // 插入边a -> b{ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;} int main(){ memset(h, -1, sizeof(h)); // 将链表头都初始化为-1，表示每一个链表都没有元素 return 0;}

四、树与图的深度优先遍历（DFS）

无论是深度优先遍历还是广度优先遍历，每个结点都只会遍历一遍。所以在实现时，会开一个bool数组来存哪些点已经被遍历过了

1.模板O(n+m)

int dfs(int u){ st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); }}

2.题目： AcWing 846.树的重心

1. 遍历每个点，依次将该点删除
2. 计算删除该点，计算剩余的各个连通块中，结点数最多的连通块中有多少个节点。（递归）
3. 对比 删除各个节点 所得出的最大值，选出这些最大值中的最小值。这个最小值所对应的删除节点即为树的重心。

关键： 通过 递归 计算 剩下的连通块中点数的最大值。
子树节点数目①用于寻找最大res；②用于求和sum

#include #include using namespace std;const int N = 100010, M = 2 * N;int ans = N, n; // ans存的是最大值的最小值，也就是最终结果int h[N], e[M], ne[M], idx = 0; // 邻接表bool st[N]; // 各节点的访问情况void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx;idx++;}// 在以u为根的子树中 结点的数量int dfs(int u) {st[u] = true; // 标记已经访问// sum用来记录当前子树点的个数，并且当前所在的这个结点也算1个，所以sum从1开始// res记录 把当前结点删除后，剩下连通块中点的最大值int sum = 1, res = 0;for (int i = h[u]; i != -1; i = ne[i]) { // 遍历当前结点的所有孩子int j = e[i];// 合法 且 未被访问过。if (!st[j]) {int childsum = dfs(j); // 用dfs 递归 算该树的子树中的结点数res = max(res, childsum);sum += childsum;}}// 循环中res只是与当前结点的子树相比较，结点删除后，上面的一大块也是连通块，所以也要与之比较// !!!!!n-mres = max(res, n - sum);ans = min(ans, res);return sum;}int main() {cin >> n; // 输入结点数memset(h, -1, sizeof(h));for (int i = 0; i < n - 1; i++) { // n-1是因为，n个结点只有n-1条边int a, b;cin >> a >> b;add(a, b);add(b, a);}dfs(1);cout << ans << endl;return 0;}

五、树与图的宽度优先遍历（BFS）

1.模板O(n+m)

queue<int> q;st[1] = true; // 表示1号点已经被遍历过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 (!st[j]) { st[j] = true; // 表示点j已经被遍历过 q.push(j); } }}

2.题目： AcWing 847.图中点的层次

由于是稀疏图，用邻接表。重边与自环无影响。

#include #include using namespace std;const int N = 100010, M = 2 * N;int n,m;int h[N], e[M], ne[M], idx = 0; // 邻接表int d[N];void add(int a, int b) {e[idx] = b;ne[idx] = h[a];ne[h[a]] = idx;idx++;}int bfs() {queue<int> q; q.push(1);// 初始化距离数组，另一方面，距离数组也能起到bool数组的作用// 即如果d[i]=-1则说明未访问过。memset(d,-1,sizeof(d));d[1]=0;while(!q.empty()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){ // 未访问过d[j]=d[t]+1; // 距离+1q.push(j);}}}return d[n];}int main() {cin >> n >> m; // 输入结点数memset(h, -1, sizeof(h));for (int i = 0; i < m; i++) { // n-1是因为，n个结点只有n-1条边int a, b;cin >> a >> b;add(a, b);}cout << bfs() <<endl;return 0;}

六、拓扑排序（针对有向图）

1. 若一个图中存在环，则这个环上的点一定不会入队列的。
2. 一个无环图，一定存在一个入度为0的点。
3. 拓扑序列不唯一。

1.思路&&模板

1. 遍历，将入度为0的点全部入队。
2. BFS逻辑中，依次遍历该点所指向的所有子节点。每次将他们的入度减一，再根据-1后的入度是否为0，将他们加入队列。
3. 如果 队尾的序号 等于 结点个数-1（因为初始时候，队尾tt=-1，所以是结点数目-1）

bool topsort(){ int hh = 0, tt = -1; // d[i] 存储点i的入度 for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (-- d[j] == 0) q[ ++ tt] = j; } } // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。 return tt == n - 1;}

2.题目： AcWing 848.有向图的拓扑序列

#include #include using namespace std;const int N = 100010;int n, m;int h[N], e[N], ne[N], idx = 0; // 邻接表int q[N], d[N]; //存储各结点的入度void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx;idx++;}bool topsort() {int hh = 0, tt = -1;for (int i = 1; i <= n; i++) {if (d[i] == 0)q[++tt] = i;}while (hh <= tt) {int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];d[j]--; // 入度-1if (d[j] == 0) {q[++tt] = j;}}}// 若全部点都放进了队列，则这个图是有拓扑序列的return tt == n - 1; //所有点都入过队列了。}int main() {cin >> n >> m; // 输入结点数memset(h, -1, sizeof(h));//memset(h, 0, sizeof(d));for (int i = 0; i < m ; i++) { // m条边int a, b;cin >> a >> b;add(a, b);d[b]++; // b结点 入度加1}if (topsort()) { // 存在拓扑序列，则输出 n个点的入队顺序for (int i = 0; i < n; i++)printf(\"%d \", q[i]);puts(\"\");} else //不存在拓扑序列puts(\"-1\");return 0;}

七、总结

1. 一中题目，由于从dfs(0)开始，所以当u==n时已经出界。
2. DFS和BFS均需要标记节点的访问情况。
   DFS一般单独开一个bool数组，
   而BFS有些题中，由于本身就需要找到最短路径（即开设一个d[N]数组记录），可以通过将其初始化为-1，实现一举两得的目的。既记录了最短路径，又当d[i]==-1时，则说明未被访问过。