赞
踩
本篇博客将介绍DFS-深度优先遍历、BFS-广度优先遍历和拓扑排序的常见题型(模板题及其扩展)。DFS和BFS是遍历图的两种方法,其中BFS多用于求最短路问题,在不要求最短时多用DFS,因为DFS的复杂度更低。而拓扑排序是图论中一种特殊的问题,用于求图中是否存在回路。
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
共一行,包含一个整数 n。
按字典序输出所有排列方案,每个方案占一行。
1≤n≤7
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include<iostream> using namespace std; const int N = 10; int path[N];//保存序列 int state[N];//数字是否被用过 int n; void dfs(int u) { if(u > n)//数字填完了,输出 { for(int i = 1; i <= n; i++)//输出方案 cout << path[i] << " "; cout << endl; } for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n { if(!state[i])//如果数字 i 没有被用过 { path[u] = i;//放入空位 state[i] = 1;//数字被用,修改状态 dfs(u + 1);//填下一个位 state[i] = 0;//回溯,取出 i } } } int main() { cin >> n; dfs(1); }
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。
共一行,包含整数 n。
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。
其中 .
表示某一个位置的方格状态为空,Q
表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
注意:行末不能有多余空格。
输出方案的顺序任意,只要不重复且没有遗漏即可。
1≤n≤9
4
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
#include <iostream> using namespace std; const int N = 20; // bool数组用来判断搜索的下一个位置是否可行 // col列,dg对角线,udg反对角线 // g[N][N]用来存路径 int n; char g[N][N]; bool col[N], dg[N], udg[N]; void dfs(int u) { // u == n 表示已经搜了n行,故输出这条路径 if (u == n) { for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl; puts(""); // 换行 return; } // 枚举u这一行,搜索合法的列 int x = u; for (int y = 0; y < n; y ++ ) // 剪枝(对于不满足要求的点,不再继续往下搜索) if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) { col[y] = dg[y - x + n] = udg[y + x] = true; g[x][y] = 'Q'; dfs(x + 1); g[x][y] = '.'; // 恢复现场 col[y] = dg[y - x + n] = udg[y + x] = false; } } 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; }
给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
第一行包含整数 n,表示树的结点数。
接下来 n−1 行,每行包含两个整数 a 和 b,表示点 a 和点 b 之间存在一条边。
输出一个整数 m,表示将重心删除后,剩余各个连通块中点数的最大值。
1≤n≤105
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
4
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5 + 10; //数据范围是10的5次方 const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边 int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点 int e[M]; //存储元素 int ne[M]; //存储列表的next值 int idx; //单链表指针 int n; //题目所给的输入,n个节点 int ans = N; //表示重心的所有的子树中,最大的子树的结点数目 bool st[N]; //记录节点是否被访问过,访问过则标记为true //a所对应的单链表中插入b a作为根 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } //返回以u为根的子树中节点的个数,包括u节点 int dfs(int u) { int res = 0; //存储 删掉某个节点之后,最大的连通子图节点数 st[u] = true; //标记访问过u节点 int sum = 1; //存储 以u为根的树 的节点数, 包括u,如图中的4号节点 //访问u的每个子节点 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; //因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过 if (!st[j]) { int s = dfs(j); // u节点的单棵子树节点数 如图中的size值 res = max(res, s); // 记录最大联通子图的节点数 sum += s; //以j为根的树 的节点数 } } //n-sum 如图中的n-size值,不包括根节点4; res = max(res, n - sum); // 选择u节点为重心,最大的 连通子图节点数 ans = min(res, ans); //遍历过的假设重心中,最小的最大联通子图的 节点数 return sum; } int main() { memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点 cin >> n; //表示树的结点数 // 题目接下来会输入,n-1行数据, // 树中是不存在环的,对于有n个节点的树,必定是n-1条边 for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); //无向图 } dfs(1); //可以任意选定一个节点开始 u<=n cout << ans << endl; return 0; }
给定一个 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
8
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 110; int n, m; int g[N][N], d[N][N];//g存储地图,d存储距离 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}, dy[4] = {0, 1, 0, -1}; //BFS宽度优先遍历 while (q.size()) { auto t = q.front(); q.pop(); //上下左右四种走法 for (int i = 0; i < 4; i ++ ) { int x = t.first + dx[i], y = t.second + dy[i]; //未超过边界(x、y的限制),且此处可走(g是0),且未走过(d是-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; 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
将 “3*3矩阵” 转化为 “字符串”
二维矩阵下标转化一维字符串下标
最终状态则是:“12345678x”
#include <iostream> #include <algorithm> #include <queue> #include <unordered_map> using namespace std; int bfs(string start) { //定义目标状态 string end = "12345678x"; //定义队列和dist数组 queue<string> q;//直接存转化后的字符串 unordered_map<string, int> d;//将字符串和数字联系在一起,字符串表示状态,数字表示距离 //初始化队列和dist数组 q.push(start); d[start] = 0; //转移方式 int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; while(q.size()) { auto t = q.front(); q.pop(); //记录当前状态的距离,如果是最终状态则返回距离 int distance = d[t]; if(t == end) return distance; //查询x在字符串中的下标,然后转换为在矩阵中的坐标 int k = t.find('x'); int x = k / 3, y = k % 3; for(int i = 0; i < 4; i++) { //求转移后x的坐标 int a = x + dx[i], b = y + dy[i]; //当前坐标没有越界 if(a >= 0 && a < 3 && b >= 0 && b < 3) { //转移x swap(t[k], t[a * 3 + b]); //如果当前状态是第一次遍历,记录距离,入队 if(!d.count(t)) { d[t] = distance + 1; q.push(t); } //还原状态,为下一种转换情况做准备 swap(t[k], t[a * 3 + b]); } } } //无法转换到目标状态,返回-1 return -1; } int main() { string c, start; //输入起始状态 for(int i = 0; i < 9; i++) { cin >> c; start += c; } cout << bfs(start) << endl; return 0; }
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。
所有边的长度都是 1,点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1。
第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从 a 走到 b 的长度为 1 的边。
输出一个整数,表示 1 号点到 n 号点的最短距离。
1≤n,m≤105
4 5
1 2
2 3
3 4
1 3
1 4
1
#include <iostream> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int h[N],ne[N], e[N], idx;//邻接表数据结构 int dist[N];//存储距离 int st[N];//标记点是否走到过 int n, m; void add(int a, int b)//邻接表存储图 { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void bfs() { memset(dist, 0x3f, sizeof(dist));//初始都没有走到过,距离无穷大 dist[1] = 0;//从1号节点开始,距离为0 queue<int> q;//队列 q.push(1);//1号节点入队列 st[1] = 1;//1到1的距离为0,已经求出 while(q.size())//对列非空,就一直往后搜索 { int t = q.front();//队头出队,找该点能到的点 q.pop(); for(int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点,i为节点索引 { int j = e[i];//通过索引i得到t能到的节点编号 if(!st[j])//如果没有遍历过 { dist[j] = dist[t] + 1;//距离为t号节点的距离+1 q.push(j);//节点入队 st[j] = 1;//入队后标记,已经遍历过了 } } } } int main() { cin >> n >>m; memset(h, -1, sizeof h);//初始化,所有节点没有后继,后继都是-1 for(int i = 0; i < m; i++)//读入所有边 { int a, b; cin >> a >> b; add(a, b);//加入邻接表 } bfs();//广度优先遍历 cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);//如果到n号节点的距离不是无穷大,输出距离,如果是无穷大,输出-1. return 0; }
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。
若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。
第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y 的有向边 (x,y)。
共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。
否则输出 −1。
1≤n,m≤105
3 3
1 2
2 3
1 3
1 2 3
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int e[N], ne[N], idx;//邻接表存储图 int h[N]; int q[N], hh = 0, tt = -1;//队列保存入度为0的点,也就是能够输出的点, int n, m;//保存图的点数和边数 int d[N];保存各个点的入度 void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void topsort(){ for(int i = 1; i <= n; i++){//遍历一遍顶点的入度。 if(d[i] == 0)//如果入度为 0, 则可以入队列 q[++tt] = i; } while(tt >= hh){//循环处理队列中点的 int a = q[hh++]; for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边 int b = e[i];//a 有一条边指向b d[b]--;//删除边后,b的入度减1 if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出,入队列 q[++tt] = b; } } if(tt == n - 1){//如果队列中的点的个数与图中点的个数相同,则可以进行拓扑排序 for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点,依次输出 cout << q[i] << " "; } } else//如果队列中的点的个数与图中点的个数不相同,则可以进行拓扑排序 cout << -1;//输出-1,代表错误 } int main(){ cin >> n >> m;//保存点的个数和边的个数 memset(h, -1, sizeof h);//初始化邻接矩阵 while (m -- ){//依次读入边 int a, b; cin >> a >> b; d[b]++;//顶点b的入度+1 add(a, b);//添加到邻接矩阵 } topsort();//进行拓扑排序 return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。