目录
背景引入
倘若我们把施工过程、生产流程、软件开发等都当成一个项目工程来对待，那么所有工程都可分为若干个子工结合而成。这些子工程之间通常会受到一定的约束，如其中一些子工程是必须在另外一些子工程完成以后才能开始。
电影制作过程中，必须要先有场地，再有导演组织演员进行拍摄。将这些零零散散的关系链接起来，形成的就是一个有向无环图。无环就是没有回路。可能有小伙伴想问，为什么一定无环了？
如图中的两个子工程a,b假如有环，a一定要先于b完成，但是因为有环，b是指向a的，b也一定要先于a完成，就矛盾了。
当图的关系过于庞大和复杂，我们要获得一条该如何进行子工程的流程图时，拓扑排序就可以大展身手
前戏——图的遍历
图的宽度优先搜索
原题传送门
题中要求最短路径，并且也指出了，每条边的的长度都是为1，即权重相等。宽度优先搜索BFS有没有在你的脑海中冒出来了
参考代码(C++版本)
#include <iostream> #include <cstring> using namespace std; const int N = 100010; int n,m; int h[N],e[N],ne[N],idx;//实现静态链表所需要的数组 int q[N],d[N];//bfs所需的队列和距离数组 void add(int a,int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } int bfs() { int hh = 0,tt = 0;//定义队头和队尾 //初始化距离数组 memset(d,-1,sizeof d); //入队1号 q[0] = 1; //标记1已被探索 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; //初始化邻接表,让表头指向空(静态链表中常用-1表示空) 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; }
图常用的表示方式有邻接矩阵和邻接表，因为邻接矩阵适合高密度的数据，所以一般是采用静态链表构造邻接表表示图。
对BFS框架和静态链表不熟悉的小伙伴可以先去看看我之前写的文章喔~🌹🌹🌹
- 数据结构——静态链表
- 算法基础系列第三章——层层推进的BFS
图的胶合剂——add()
add函数的作用是将新的点连接到邻接表上。
进入下一个模块
拓扑排序
典例
原题传送门
参考代码(C++版本)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n,m; int h[N],e[N],ne[N],idx; int q[N],d[N];//表示队列和度 void add(int a,int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } bool toposort() { int hh = 0,tt = -1;//定义队列的队头hh 和 队尾tt //把入度为0的点全部入队 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]; d[j] --; if(!d[j]) q[++ tt] = j; } } return tt == n-1; //当尾指针迭代到最后一个数据了，证明形成一个拓扑序列了 } int main() { cin >>n >>m; memset(h,-1,sizeof h); //接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。 for(int i = 0; i < m;i++) { int a, b; cin >> a >> b; add(a,b); d[b] ++;//因为是将b接在a的后面，所以b的入度得增加 } if(toposort()) { //输出一个拓扑排序 for(int i = 0; i <n;i++) printf("%d ",q[i]); puts(""); }else { puts("-1"); } return 0; }
拓扑序列实现框架
1.使用cstring中的库函数memset快速初始化邻接表
memset(h,-1,sizeof h);
2.应题意将数据连接，形成一个图，连接过程中，注意调整各点的入度（入度是指向这个结点的边数）
add(a,b); d[b] ++;//因为是将b接在a的后面，所以b的入度要增加
3.将所有入度为0的点放入队列
for(int i = 1;i <= n;i++) if(!d[i]) q[++ tt] = i;
4.当队列不空：取出队头元素，拓展队头
//拓展队头 for(int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; d[j] --; if(!d[j]) q[++ tt] = j; }
疑点剖析
相较于原本的BFS框架而言，变化较大的是拓展队头这块的逻辑
在迷宫问题中是对四个方向进行拓展，在拓扑序列中，是对这个队头t所在的邻接表进行拓展。
1.将队头t所在的邻接表的头指针的地址(本质是数组的下标)赋值给i，当指针i没有指向空，进入循环，更新循环变量i,使其指向它的后一位
for(int i = h[t]; i != -1; i = ne[i])
2.获取拓展信息的具体数值。e[N]中存储的是每个结点的数值。通过拓展获得的下标i放到e[N]中就可以匹配到具体的数值了。再将这个数值的度减1
int j = e[i]; d[j] --;
3.倘若减1之后，入度为0。就符合进入队列的标准，将其入对
if(!d[j]) q[++ tt] = j;
举一反三
一、家谱树——信息学奥赛一本通-T1351
原题传送门
参考代码(C++版本)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 550; int n; int h[N],e[N],ne[N],idx; int q[N],d[N]; void add(int a,int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } void toposort() { int hh = 0,tt = -1; //先把所有度为0的点入队 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]; d[j]--; if(!d[j]) q[++ tt] = j; } } } int main() { cin >> n; memset(h,-1,sizeof h); for(int i = 1; i <= n;i++) { int a; while( cin >> a, a!= 0 ) { add(i,a); d[a] ++; } } toposort(); for(int i = 0; i <n;i++) printf("%d ",q[i]); return 0; }
样例剖析
家谱树就和我们上文的典例几乎一模一样了，换汤不换药。
一个拓扑序列就正好满足题目要求的输出序列。
小总结
当题目中给了杂乱的关系图，最后让输出一份有顺序的序列，记得可以用拓扑排序实现
二、奖金——信息学奥赛一本通-T1352
原题传送门
参考代码(C++版本)
#include <iostream> #include <cstring> using namespace std; const int N = 20010; int n,m; int h[N],e[N],ne[N],idx; int q[N],d[N]; int dist[N];//记录每个人奖金数额的数组 void add(int a,int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } bool topsort() { int hh = 0, tt = -1; 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]; d[j] --; if(!d[j]) { q[++ tt] = j; } } } return tt == n-1;//tt 是尾指针，等于n-1说明有n个点形成一个拓扑序列了，否则就有环 } int main() { cin >>n >>m; memset(h,-1,sizeof h); while(m--) { int a,b; cin >> a >>b; add(b,a); d[a] ++; } //做拓扑排序 if(!topsort()) puts("Poor Xed"); else {//计算最长路 for(int i =1; i <= n ;i++) dist[i] = 100;//初始化每个员工的奖金 for(int i = 0; i < n;i++) { int j = q[i];//取出队列中存的元素 for(int k = h[j] ; ~k; k = ne[k]) dist[e[k]] = max(dist[e[k]],dist[j] +1);//1是增加的最小奖金增量，此题也可以看做权重 } int res = 0; for(int i = 1;i <= n;i++) res += dist[i]; cout << res << endl; } return 0; }
样例剖析
奖金这道题就不再是简单暴力的直接求拓扑序列了，这里要对求出来的拓扑序列作为已知条件，进而求解出答案。
难点一：构建图的细节
int a,b; cin >> a >>b; add(b,a); d[a] ++;
题干要求是为员工 a 的奖金应该比 b 高。处理为让a接在b后面，也就是增加a的入度，这种让奖金被最加的最高放到后面，在计算的时候就会更方便
难点二：计算最长路
可能有小伙伴会疑问，题目要求我们求最省钱的方式，你为什么要求最长路了？思想和高中数学的解析几何求最值很像似。一个开头向下的二次函数，假如在顶点算出来的值是可以满足，那其他点也肯定满足。同理，让最糟糕的时候都满足最省钱的方案，那么其他的情况也肯定能满足
操作流程：
取出存在队列中的每一个数据元素。
int j = q[i];//取出队列中存的元素
放到邻接表中，求得这个元素的下一位元素
for(int k = h[j] ; ~k; k = ne[k])
计算下一位的奖金
dist[e[k]] = max(dist[e[k]],dist[j] +1)
因为下一位员工比当前这个员工奖金高，又为了省钱，所以用dist[j] +1元表示下一位员工可获得的奖金
求出总和，
int res = 0; for(int i = 1;i <= n;i++) res += dist[i]; cout << res << endl;
三、可达性统计——算法竞赛进阶指南
原题传送门
参考代码(C++版本)
#include <iostream> #include <cstring> #include <algorithm> #include <bitset> using namespace std; const int N = 30010; int n ,m; int h[N],e[N],ne[N],idx;//数组模拟的邻接表 int q[N],d[N];//队列和度 bitset<N> f[N];//f[i]表示这个点可以达到的集合，这里使用二进制压位，二进制压位的规则是1是可以到达，0是不能到达 void add(int a, int b) { e[idx] = b, ne[idx] = h[a],h[a] = idx ++; } void topsort() { int hh = 0, tt = -1; //把度为0的点入队 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; } } } int main() { ios::sync_with_stdio(false); cin >> n >> m; memset(h,-1,sizeof h);//初始化邻接表 while(m--) { int a ,b; cin >>a >>b; add(a,b); d[b] ++; } //利用拓扑序列的性质实现倒推回去，那么此时我需要做的就是压位 topsort(); //从拓扑序列中取出每一个点 for(int i = n-1;i >= 0;i--) { int j = q[i]; f[j][j] = 1;//表示j可以到j这个点，因为对于二进制的而言，要么就是[j-0]表示不能到达，要么就[j-1]能到达 for(int k = h[j] ; k != -1;k = ne[k]) f[j] |= f[e[k]];//把j能到的点和j之后的点能到的点通过或运算合并在一起 } for(int i = 1; i <= n;i++) cout << f[i].count() <<endl; return 0; }
样例剖析
这道题是拓扑排序的再深化了。拓扑排序在这里只是被利用起来的一步工具，需要使用它获得一个拓扑序列，然后我们从拓扑序列的尾端递推算回去每个点可以到达的点的数量
逐步讲解
一、
头文件将需要用的一些声明呀、数据呀，噼里啪啦的敲上来
#include <iostream> #include <cstring> #include <algorithm> #include <bitset> using namespace std; const int N = 30010; int n ,m; int h[N],e[N],ne[N],idx;//数组模拟的邻接表 int q[N],d[N];//队列和度 bitset<N> f[N];//f[i]表示这个点可以达到的集合，这里使用二进制压位，二进制压位的规则是1是可以到达，0是不能到达
需要介绍STL容器中的bitset，简单来说，它能将传入的一个无符号数转成一个二进制的数列。构造时，需在<>中表明bitset 的大小(即size)。
因为数据比较大，此时记得算一下规模，防止出现TLE或者MLE。
假如直接递推回来，就需要大约要M * M (题干 中说M<=30000)的内存,假如拉到极限，30000*30000个int，1e6个int 是4M,因此会超出限定的256MB
考虑采用二进制实现状态压缩，一个int可以转成32位的二进制，即一个int就可以表示32个数，此时再算，大约是要120MB左右，符合要求了。
二、
书写求拓扑序列的框架
memset(h,-1,sizeof h);//初始化邻接表 while(m--) { int a ,b; cin >>a >>b; add(a,b); d[b] ++; } //利用拓扑序列的性质实现倒推回去 topsort();
三、
取出拓扑序列中的每个点，放到存放i这个点能到达的点的数组f[i]。结合"或运算"实现"并上"的功能，求它能到达的点的个数
//从倒着拓扑序列中取出每一个点 for(int i = n-1;i >= 0;i--) { int j = q[i]; f[j][j] = 1; for(int k = h[j] ; k != -1;k = ne[k]) f[j] |= f[e[k]]; } for(int i = 1; i <= n;i++) cout << f[i].count() <<endl;
位运算状态压缩的规则是0表示不能到达，1表示可以到达。
简单来说，就是以前的每一个数，比如int型的数值2999现在可以用一个位二进制表示了，结合拓扑图求出来的序列，最后算出来某一点可以到达的点的数量
f[j][j]表示现在获取的这个数据是能到达它自身，而对于之后的点，则是由0和1表示能不能到到达
总结
拓扑排序在算法竞赛中很少直接出裸题让我们直接把分薅到手，正如我逐渐逐渐带入的例题一样，拓扑排序往往只会作为一条件加以利用，就像高考数学解析几何第一小问就是求曲线方程，第二问把第一问作为条件。
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)