当前位置：首页 > news >正文

拓扑排序：有向无环图的排队艺术

news 2026/8/2 17:45:43

1.引入：身边的拓扑排序

做番茄炒蛋：

先洗番茄，再切番茄
先打蛋，再搅拌蛋液
切番茄和搅拌蛋液可以同时准备
都准备好之后，才能下锅炒

拓扑排序就能给我们提供一种合理的顺序，如：

洗番茄 → 切番茄 → 打蛋 → 搅拌蛋液 → 下锅翻炒

2.什么是拓扑排序

作用:对有向无环图的所有顶点进行排序
排序标准：假如\(A\)节点指向\(B\)节点，那么\(A\)节点一定排在\(B\)节点之前

例子：

通过~~简单的~~推理，我们可以发现，这个有向无环图中的一种合理顺序为：

2 → 4 → 5 → 3 → 1

3.拓扑排序的实现方法

对于上面的例子，我们可以检测每个节点的入度（即有多少个节点指向此节点）：

节点1的入度为： 2
节点2的入度为： 0
节点3的入度为： 2
节点4的入度为： 1
节点5的入度为： 2

第一步：

在图中找出入度为0的节点，放入q队列：

第二步：

将队列的第一个数放入答案队列的末尾，并将此节点指向的所有节点入度减一，并将入度为0的节点加入队列（不重复入队）：

第三步：

重复步骤2，直到队列q为空：

↓

此时队列q为空，答案为队列ans

3.代码实现

#include<bits/stdc++.h>//万能头文件
using namespace std;
vector<int>e[105];//存储有向图中边的关系，e[i]中存储第i个节点指向的所有节点
int n;
queue<int>q;//临时队列，存储入度为0的节点
int d[105];//存储入度
int vis[105];//是否访问过
int main() {cin>>n;//输入边数/节点数for(int i=1;i<=n;i++) {while(1) {  int a;cin>>a;e[i].push_back(a);//存储有向边if(a==0) {break;}d[a]++;//记录入度}}for(int i=1;i<=n;i++) {if(d[i]==0) {q.push(i);//将入度为0的加入队列vis[i]=1;//标记以访问}}while(!q.empty()) {//队列非空int x=q.front();//取出队列第一项q.pop();cout<<x<<" ";//输出答案for(int i:e[x]) {//枚举节点x指向的所有节点if(vis[i]) continue;//确保节点未被访问过d[i]--;//将入度减少1if(d[i]==0) {//入度为0vis[i]=1;//标记已访问q.push(i);//加入队列}}}return 0;
}

4.例题讲解

P4017 最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 \(1\) 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 \(80112002\) 的结果。

输入格式

第一行，两个正整数 \(n\)、\(m\)，表示生物种类 \(n\) 和吃与被吃的关系数 \(m\)。

接下来 \(m\) 行，每行两个正整数，表示被吃的生物 A 和吃 A 的生物 B。

输出格式

一行一个整数，为最大食物链数量模上 \(80112002\) 的结果。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

各测试点满足以下约定：

测试点编号	\(n\)	\(m\)
\(1,2\)	\(\le 40\)	\(\le 400\)
\(3,4\)	\(\le 100\)	\(\le 2\times 10^3\)
\(5,6\)	\(\le 10^3\)	\(\le 6\times 10^4\)
\(7,8\)	\(\le 2\times 10^3\)	\(\le 2\times 10^5\)
\(9,10\)	\(\le 5\times 10^3\)	\(\le 5\times 10^5\)

对于 \(100\%\) 的数据，\(1 \le n \le 5\times 10^3,1\le m \le 5\times 10^5\)

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE）

4.1主要思路

拓扑排序+dp

状态定义：\(dp[i]\) 表示到达节点\(i\)的路径数
初始化：将所有入度为0的点标记为1
状态转移方程：\(dp[i]=所有指向i节点的路径数量总和\)

4.2代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=80112002;
vector<ll>e[5005];//存储有向边
ll n,m;//n为节点数，m为边数
queue<ll>q;//临时存储入度为0的节点
ll d[5005],s[5005],c[5005];//d存储入度，s存储答案，c存储出度（即此节点指向多少个节点）
int main() {cin>>n>>m;//输入for(ll i=1;i<=m;i++) {ll a,b;cin>>a>>b;//输入e[a].push_back(b);//节点a指向节点bd[b]++;//更新入度c[a]++;//更新初读}for(ll i=1;i<=n;i++) {if(d[i]==0) {//检测是否入度为0q.push(i);//存入队列s[i]=1;//标记路径数量为1}}ll ans=0;//答案，初始化为0while(!q.empty()) {//队列不为空ll x=q.front();//获取队首元素q.pop();for(ll i:e[x]) {//遍历节点x指向的所有节点d[i]--;//入度减1s[i]+=s[x];//更新到达节点i的路径数量s[i]%=N;//取modif(d[i]==0) {q.push(i);//加入队列}}}for(int i=1;i<=n;i++) {if(c[i]==0) {//判断初读ans+=s[i];//答案为出度为0的所有元素路径数量总和ans%=N;}}cout<<ans;//输出答案return 0;
}