-
第三章搜索与图论（一）
框架
DFS与BFS区别
DFS:
执着：一直走到头，回去的时候边回去边看能不能向下走
BFS:
稳重：每次只扩展一层，不会离家太远
算法 数据结构 空间 特征 DFS stack O(h) 不具有最短性 BFS queue O(2h)、指数级别 “最短路” DFS
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- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
步骤
- 找到第一个解
-
回溯
-
最终结果
没有必要区分DFS与递归，DFS就是递归。
虽然看上去是树的形式，但存储的话只会存当前路径，回溯的时候就没有了。
没有必要把整颗树存储下来。
不需要真的把栈写出来，系统会为我们做回溯。写在递归函数中，有隐藏栈来维护，不需要开额外空间。
回溯中一定要注意恢复现场，下来的时候是什么样子，回去之后就是什么样子
#includeusing namespace std; const int N = 10; int n; //将状态[路径]存储下来，当向下搜时，path上数字会逐渐填满 int path[N]; //需要知道当前位置上可以填哪些数，即清楚哪些数已经用过了。等于true,表示该点被用过了 bool st[N]; void dfs(int u) { //一开始在第0个位置，当到达第n个位置，表明均填满，此时输出即可 if(u == n) { for(int i = 0 ; i < n;i++) printf("%d ",path[i]); //输出空行 puts(""); return; } for(int i = 1;i<=n;i++) //找到一个没有被用过的数，只有没有用过的才可以使用 if(!st[i]) { //将数字放到当前位置上去 path[u] = i; //记录i已经被用过了 st[i] = true; //将状态处理好后，递归至下一层 dfs(u+1); //dfs结束时，表明下面的所有路都走完了，就要回溯； //回溯时注意恢复现场。出去时什么样，回来时什么样，回溯后继续运行for循环 // path[u] = 0没有什么用，因为path[u]的值会被不断覆盖掉。不管是几都没问题，因此没必要恢复 //path[u] = 0; st[i] = false; } } int main() { 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
n皇后
n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。- 1
现在给定整数 n，请你输出所有的满足条件的棋子摆法。 输入格式 共一行，包含整数 n。 输出格式 每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。 其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。 每个方案输出完成后，输出一个空行。 注意：行末不能有多余空格。 输出方案的顺序任意，只要不重复且没有遗漏即可。 数据范围 1≤n≤9 输入样例： 4 输出样例： .Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..- 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
重要的是顺序：顺序一定要想清楚
-
全排列
每一行只有一个皇后
第一行皇后可以放在哪一列
注意剪枝
提前判断当前方案是不合法的，停止向下搜索，直接回溯
对角线
两种对角线的截距b有两种：
y-x:截距不能是负数；所以添加偏移量ny+x
对角线的数目是2*N-1
#includeusing namespace std; const int N = 20; int n; //存储方案 char g[N][N]; //状态数组：列、正对角线、反对角线 bool col[N],dg[N],udg[N]; //对行进行遍历 void dfs(int u) { //当到达第u行，当找到一组方案时 if(u == n) { //输出 for(int i = 0;i<n;i++) puts(g[i]); puts(""); return; } //从第一列开始枚举 for(int i = 0 ;i<n;i++) //这一列之前没有放过并且对角线上没有放过并且反对角线上没有放过 //i代表y，u代表x 反对角线 -x+y+n if(!col[i] && !dg[u+i] && !udg[-u + i +n]) { //在第u行第i列放置皇后 g[u][i] = 'Q'; //第i列为true，表示这一列/对角线/反对角线上已经有皇后了 col[i] = dg[u+i] = udg[-u+i+n] = true; dfs(u+1); //恢复现场 col[i] = dg[u+i] = udg[-u+i+n] = 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 ; } - 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
时间复杂度：
n*n！ -
上一种方式经过一步分析，即每一行放置一个皇后。
也可以采用一种更原始的方式进行枚举八皇后问题。
一格格枚举，每个节点代表一个格子
n2个格子
考虑格子的边界问题：如果出界，直接返回
时间复杂度：2n2
#includeusing namespace std; 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) { //到达y的边界后，y置为0，跳转至下一行 if(y == n) y = 0,x++; //枚举到最后一行，需要停止 if(x == n) { //皇后个数等于n，找到一组解 //s有可能小于n，有可能一个皇后都没有摆，只有n个皇后才有解 if(s == n) { for(int i = 0; i
- 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
- 59
- 60
- 61
- 62
BFS
一圈一圈，搜索的距离离当前起点越来越远
给定一个 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- 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
样例：
BFS：
每个数字表示它是第几层被扩展到的。
若采用深搜，结果不一定对。可以保证找到终点，但不能保证是最短的
深搜没有固定框架但宽搜有固定框架。
- 将初始状态放到队列中
- 写while循环：队列不为空
- 每次把队头拿出来
- 扩展队头
- 结束
假设绿点是队头，尝试向上下左右四个方向拓展
用向量表示方向
上 （-1，0）//横坐标减一，纵坐标不变 右 （0，+1）//横坐标不变，纵坐标加一 下 （+1，0）//横坐标加一，纵坐标不变 左 （0，-1）//横坐标不变，纵坐标减一- 1
- 2
- 3
- 4
#include#include #include //一般需要队列，此处手写队列 //#include using namespace std; //用于表示(x,y) typedef pair<int,int> PII; const int N = 110; int n,m; int g[N][N]; //存储图,不改变图的信息，只改变队列 int d[N][N]; //存储每个点到起点的距离 //队列，用于存储当前点 PII q[N*N]; int bfs() { //队头hh，队尾tt,由于队列中现在存放第一个数据，因此tt = 0 ；空队列tt = -1; q[0] = {0,0}; int hh = 0 ,tt = 0; //初始化为-1 memset(d,-1,sizeof d); //从[0,0]点开始走，一开始距离为0 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++) { //(x,y)表示沿着该方向可以走到哪个点 int x = t.first + dx[i],y = t.second + dy[i]; //判断点是否在边界以内 并且 点是可以走的 并且 这个点还没有走过 // 如果已经走过，表明该点不是第一次搜到，bfs是第一次搜到的点才是最短距离 // 注意 x的边界为n，y的边界为m if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) { //当前点的距离是之前点的距离加1 d[x][y] = d[t.first][t.second] + 1; //将点添加至队列中 q[++tt] = {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; } - 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
- 59
- 60
- 61
- 62
- 63
- 64
如何显示路径–新建一个变量【数组】存储Prev,记录该位置上的点是由上面哪个点扩展而来的
#include#include #include //一般需要队列，此处手写队列 //#include using namespace std; //用于表示(x,y) typedef pair<int,int> PII; const int N = 110; int n,m; int g[N][N]; //存储图,不改变图的信息，只改变队列 int d[N][N]; //存储每个点到起点的距离 //队列，用于存储当前点 PII q[N*N]; //最后用于显示路径，每个点存储上一个点的信息，所以每个元素是一个坐标 PII Prev[N][N]; int bfs() { //队头hh，队尾tt,由于队列中现在存放第一个数据，因此tt = 0 ；空队列tt = -1; q[0] = {0,0}; int hh = 0 ,tt = 0; //初始化为-1 memset(d,-1,sizeof d); //从[0,0]点开始走，一开始距离为0 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++) { //(x,y)表示沿着该方向可以走到哪个点 int x = t.first + dx[i],y = t.second + dy[i]; //判断点是否在边界以内 并且 点是可以走的 并且 这个点还没有走过 // 如果已经走过，表明该点不是第一次搜到，bfs是第一次搜到的点才是最短距离 // 注意 x的边界为n，y的边界为m if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) { //当前点的距离是之前点的距离加1 d[x][y] = d[t.first][t.second] + 1; //Prev[x][y]中存储上一个点 Prev[x][y] = t; //将点添加至队列中 q[++tt] = {x,y}; } } } //从结尾向前输出 int x= n-1,y = m-1; //当x y不同时等于0的时候，前进。x、y同时为0，表明到达起点 while(x||y) { cout<<x<<' '<<y<<endl; //获取上一个点，二维点用auto较为方便 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<m;j++) cin>>g[i][j]; 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
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
DP问题与最短路问题是互通的，dp问题可以看作是一种特殊的最短路问题。
树和图的遍历
树和图的存储
树是一种特殊的图，即无环连通图，因此只需要考虑图的存储方式即可。
图可以分为有向图与无向图。无向图可以建立两个有向边来表示。因此无向图是一种特殊的有向图。只需要考虑有向图如何存储。
存储方式 空间 场景 邻接矩阵 n2 适合存储稠密矩阵 邻接表[每个节点有一个单链表] 举例：四个点，开四个单链表。
每个链表存储直接可以到达的点。单链表内部次序是无关紧要的。
当添加新的边时2->3，在链表头部进行插入节点
添加后邻接表
注意
- 邻接表使用数组而不使用vector : vector的效率不如数组快
- 区分使用cin、scanf的场景：当输入输出的规模在 100 0000[一百万]时 ，才必须用scanf，否则两者效率都差不多
#include#include #include using namespace std; const int N = 100010,M = N * 2; /* h--N个链表的链表头 e--存储链表的值，在邻接表中表示连接的节点编号，在图中表现为所有的边。 ne--每个节点的next值 */ int h[N],e[M],ne[M],idx; //插入一条边：a->b:即在a节点对应的链表中插入节点b void add(int a, int b) { e[idx] = b;ne[idx] = h[a];h[a] = idx++; } int main() { //链表初始化：将所有的链表头初始化为-1即可 memset(h,-1,sizeof h); } - 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
数和图的遍历
遍历时每个点只遍历一次
深度优先遍历
有向图
遍历顺序
#include#include #include using namespace std; const int N = 100010,M = N * 2; /* h--N个链表的链表头 e--存储链表的值，在邻接表中表示连接的节点编号，在图中表现为所有的边。 ne--每个节点的next值 */ int h[N],e[M],ne[M],idx; //每个点只需要遍历一次，需要存储bool数组表示哪些点已经遍历过了 bool st[N]; //插入一条边：a->b:即在a节点对应的链表中插入节点b void add(int a, int b) { e[idx] = b;ne[idx] = h[a];h[a] = idx++; } //u表示当前已经dfs到的点 void dfs(int u) { //首先更新状态，标记当前点已经被搜索过了 st[u] = true; //遍历u的所有出边,与遍历单链表相同 for(int i = h[u];i != -1; i = ne[i]) { //获取节点值，即对应的图中节点编号 int j = e[i]; //判断条件,如果j没有被搜过，则继续搜，一条路走到黑 if(!st[j]) dfs(j); } } int main() { //链表初始化：将所有的链表头初始化为-1即可 memset(h,-1,sizeof h); //从第一个节点开始搜素 dfs(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
846 树的重心 给定一颗树，树中包含 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- 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
- 无向图，建立相反方向的边
- 输出最小的最大值
举例：说明重心是什么
依次枚举删除每个点后剩余部分的最大值
点 连通块最大值 1 4 2 6 4 5 
做法：
每个点删除后，剩余连通块的最大值，在所有点中找最小的
深度优先遍历可以快速算出每棵子树的大小
以去除4为例
时间复杂度：O(n+m)
#include#include #include using namespace std; const int N = 100010,M = N * 2; /* h--N个链表的链表头 e--存储链表的值，在邻接表中表示连接的节点编号，在图中表现为所有的边。 ne--每个节点的next值 */ int h[N],e[M],ne[M],idx; int n; //记录全局的答案，表明最小的最大值 int ans = N; //每个点只需要遍历一次，需要存储bool数组表示哪些点已经遍历过了 bool st[N]; //插入一条边：a->b:即在a节点对应的链表中插入节点b void add(int a, int b) { e[idx] = b;ne[idx] = h[a];h[a] = idx++; } //dfs返回以u为根的子树中点的数量 //u表示当前已经dfs到的点 int dfs(int u) { //首先更新状态，标记当前点已经被搜索过了 st[u] = true; //sum:记录当前以u为树根的子树的大小，用于返回值 //res:将该点删除后连通块的最大值，初始化为0 //注：定义变量后一定要及时初始化 int sum = 1,res = 0; //遍历u的所有出边,与遍历单链表相同 for(int i = h[u];i != -1; i = ne[i]) { //获取节点值，即对应的图中节点编号 int j = e[i]; //判断条件,如果j没有被搜过，则继续搜，一条路走到黑 if(!st[j]) { //s表示当前子树的大小 int s = dfs(j); //当前子树也是一个连通块 res = max(res,s); //当前子树是以u为根节点树的一部分 sum += s; } } //计算剩余的连通块的数量 n - sum res = max(res, n - sum); //最后，res存储删除该点后最大的连通块点数 ans = min(ans,res); return sum; } int main() { //处理输入输出 cin>>n; //链表初始化：将所有的链表头初始化为-1即可 memset(h,-1,sizeof h); for(int i = 0;i < n;i++) { int a,b; cin>>a>>b; add(a,b),add(b,a); } //从第一个节点开始搜素 //为什么不是0：idx存放的是边，也就是下标，节点为对应的值。图的节点由输入决定,输入的节点最小为1。以那个点开始搜索都是一样的,以哪个点为根节点均可以 dfs(1); cout<<ans<<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
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
宽度优先遍历
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mTfsenij-1659948153547)(https://gitee.com/jgyong/blogimg/raw/master/img/image-20220808105008157.png)]
847 图中点的层次 给定一个 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- 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
宽搜图的基本框架：
- 将初始状态放到队列中 -->将1号点放至队列中
- 初始化：距离[其他点的距离为-1，头结点的距离为0]
- 写while循环：队列不为空
- 每次取得队头元素
- 扩展队头：扩展所有能到的点
- 如果x没有被遍历过[因为只有第一次遍历才是最短路径，以后的遍历都不是了]
- x入队
- 更新x的距离
- 如果x没有被遍历过[因为只有第一次遍历才是最短路径，以后的遍历都不是了]
- 结束
最重要的是：关注思想
#include#include using namespace std; //有向图，节点与边的上限可以都设置为N const int N = 100010; int n,m; int h[N],e[N],ne[N],idx; int d[N],q[N]; void add(int a,int b) { e[idx] = b;ne[idx] = h[a];h[a] = idx++; } int bfs() { //将0节点放置在队列中 int hh = 0,tt=0; //将1号节点放在队列的0号位置 q[0] = 1; //初始化距离 memset(d,-1,sizeof(d)); //d[节点]：初始化1号节点距离为0 d[1] = 0; while(hh <= tt) { //取头结点 int t = q[hh++]; //拓展每个点的临边 for(int i = h[t];i != -1;i = ne[i]) { //获取节点，进行判断 int j = e[i]; if(d[j] == -1) { d[j] = d[t] + 1; q[++tt] = j; } } } return d[n]; } int main() { cin>>n>>m; memset(h,-1,sizeof(h)); for(int i = 0 ;i < m;i++) { 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
- 59
- 60
- 61
- 62
图的宽搜应用
最经典应用为求拓扑距
848. 有向图的拓扑序列 给定一个 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- 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
拓扑序列针对有向图而言，无向图没有拓扑序列
举例
对于每条边，起点都在终点前面，它就是个拓扑序列。
拓扑序列对应图中每个边都是由前指向后的。
并不是所有的图都有拓扑序列。有环的图没有拓扑序列。
有向无环图一定存在拓扑序列的，因此有向无环图又被称为拓扑图。
度数：
有向图中每个点有两个度
入度：一个点有几条边进来，边数叫做入度
出度：一个点有几条边出去，边数叫做出度
如何求拓扑序列？
拓扑序列都是由前指向后，入度为0的点都可以作为起点
入度为0，没有一条边指向我，没有任何一个节点在我前面，所有点都可以排在最前面的位置
如果有环的话，所有点的入度都不是0
框架：
- 将所有入度为0的点入队
- 宽搜
- 队列不空
- 取队头 t
- 枚举t的所有出边 t->j
- 删掉边，使得后面节点j的入度–
- 如果j的入度为0[j前面的点都拍好序 放好了]
- j没有任何限制，j入队
- 队列不空
没有环的图一定可以依次解决每一个点。
一个有向无环图，一定至少存在一个入度为0的点
有向无环图，删除一个点后还是有向无环图。
#include#include using namespace std; const int N = 100010; int n,m; int h[N],e[N],ne[N],idx; //q存储队列 int q[N]; //d存储入度 int d[N]; void add(int a,int b) { e[idx] = b,ne[idx]= h[a],h[a] = idx++; } bool topsort() { int hh = 0,tt = -1; //遍历所有点，将所有入度为0的点插入到队列中去 for(int i = 1;i <= n;i++) if(!d[i]) //从队尾插入 q[++tt] = i; //while队列不空 while(hh <= tt) { //取出队头元素 int t =q[hh++]; for(int i = h[t];i != -1;i = ne[i]) { //找到出边 int j = e[i]; //因为弹出队头，所以之后点的入度减一 d[j]--; //如果入度为0，添加至队列 if(d[j] == 0) q[++tt] = j; } } //如果所有点都进入队列，表明是有向无环图，n个点，一开始tt = -1 //队列中次序就是拓扑序。出队的顺序是拓扑序。出队只是将指针从前向后移动一位，前面的顺序都是不变的。因此遍历完成后q中顺序就是拓扑序 return tt == n-1; } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i = 0;i < m;i++) { int a,b; cin>>a>>b; add(a,b); //更新入度 d[b]++; } if(topsort()) { for(int i = 0;i < n;i++) printf("%d ",q[i]); puts(""); } else puts("-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
- 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
- 59
- 60
- 61
- 62
- 63
- 64
- 65
题目的答案并不是唯一的
python re findall search finditer complie 预加载
【Educoder作业】C&C++控制结构实训
C++实战-Linux多线程(入门到精通)
软件测试/测试开发丨探索AI与测试报告的完美结合，提升工作效率
哈夫曼树的题
mysql secure_file_priv 属性相关的文件读写权限问题
毕业设计 基于大数据的服务器数据分析与可视化系统 -python 可视化 大数据
R 语言读写文件
雨量水位监测显示屏内涝状况提前掌握