拓扑排序算法
用unordered_map就比较万能了，完全像刚才想象出来的邻接表结构，我们这里是一个int的数后面挂了一个int数组，那不就和一个节点挂着一个节点的效果一样的吗。我们可以把给的信息抽象称一张有向图，题目问能否完成所有课程学习意思就是能不能把这个课程排个序，说白了就是能否拓扑排序，能否拓扑排序也就是是否这个图是否是有向无环图 —> 有向图中是否有环？，有向图就是边都是有方向的。直接对图来一次拓扑
目录
题目二——210. 课程表 II - 力扣（LeetCode）
题目三——B3644 【模板】拓扑排序 / 家谱树 - 洛谷
一.预备知识
1.1.有向无环图
要知道什么拓扑排序我们首先要知道什么是有向无环图，有向无环图我们看名字其实就很容易理解，有向就是有方向，无环就是没有环形结构。
在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。
有向无环图指的是有方向，但没有环的图。
换句话说，若⼀个有向图中不存在回路，则称为有向⽆环图(directedacyclinegraph)，简称DAG图。
图就是一个顶点和边连接而成的一个数据结构，有向图就是边都是有方向的。有向无环图就是图中是没有环的。如不能从1->2->3，3->2->4 所以这个图就是一个有向无环图。
如 4->5->6 是可以走通的，这就不是有向无环图了。
接下来我们来介绍一下有向图中的一些专业术语：
- 入度（Indegree）：一个顶点的入度是指有多少条边指向这个顶点。换句话说，它表示该顶点有多少个直接前驱节点。（简单来说就是对于一个顶点来说，所有指向他的边之和）
- 出度（Outdegree）：一个顶点的出度是指从这个顶点出发有多少条边。也就是说，它表示该顶点有多少个直接后继节点。（简单来说对于一个顶点来说，，这个顶点往外伸出的边的总和）
1.2.AOV网
接下来我们来说说AOV网，也就是顶点活动图。
AOV网也叫做顶点活动图，它其实是一个有向无环的一个应用。
在有向无环图中，用顶点来表示一个活动，用边来表示执行活动的先后顺序的图结构
比如我想洗菜，我得先买菜，我想腌肉需要先买菜和准备厨具。。
在这种有向图中，⽤顶点表⽰活动，⽤有向边< >表⽰活动
必须先于活动
进⾏，这种有 向图叫做顶点表⽰活动的⽹络(Activity On Vertex Network)，简称AOV⽹。
AOV⽹中不能有回路，否则就不能确定回路中的活动究竟哪个先实施。因此⼀个可⾏的AOV⽹必须是 有向⽆环图。
1.3.拓扑排序
概念：略
拓扑排序大白话意思就是，在AOV网中找到做事情的先后顺序。
可以看到在这些活动中，其中一些活动必须在某些活动执行之后才能执行，比如说炒菜，必须先切菜，腌肉。所以在整个工程中这个炒菜绝对不可能先干。
那些活动可以先干呢？可以看到准备厨具、买菜可以先干，原因就是并没有边执行它们俩。可以先准备厨具，或者先买菜。所以从这里就可以发现一点，拓扑排序的结果可能不是唯一的！
如果先买菜，买完菜之后与买菜相连的箭头就可以删掉了，因为买完菜就可以解锁洗菜的操作了。所以这个箭头就可以删去了。。
接下来可以准备厨具或者洗菜，原因是它俩都没有其他条件来限制。可以任选一个。
接下来只能洗菜。。。。。同理重复上面操作，最后我们就可以得到这样的做事情先后的序列，这也是就是拓扑排序的序列。找到做事情的先后顺序。
如何进行拓扑排序？
- 找出图中入度为 0 的点，然后输出
- 删除与该点相连的边
- 重复1、2操作，直到图中没有点或者没有入度为 0 的点为止
图中没有点理解，所有活动都找完了可以停止了此时的序列就是拓扑排序的序列。
- 图中没有入度为 0 的点是怎么回事？
其实就是在这个拓扑排序中可能面对的不是有向无环图，是有环形结构的。
比如下面这个图，刚开始并不知道这个有向图是不是有环的，所以我们可以先做一下拓扑排序
当把1、3、2拿出来之后，发现剩下的都拿不出来了。原因就是4、5、6形成一个环路，是没有入度为0的边。
因此这个结束条件还需要加上直到图中没有入度为 0 的点为止 原因就是可能有环！
所以说拓扑排序有一个特别重要的应用，判断有向图中是否有环。
如何判断有向图中是否有环？
直接对图来一次拓扑排序，当拓扑排序过程中发现没有入度为0的点的时候，但是图中还有剩余点的时候，此时这个图中一定会有环形结构。
1.4.实现拓扑排序
借助队列，来一次 BFS 即可
初始化：把所有入度为 0 的点加入到队列中
当队列不为空的时候
- 拿出队头元素，加入到最终结果中
- 删除与该元素相连的边
- 判断：与删除边相连的点，是否入度变成 0 ，如果入度为 0，加入到队列中
这里还有一个问题没说，如何建图？ 如何表示一个点的入度呢？下面的题在说。建完图然后搞拓扑排序。
题目一——207. 课程表 - 力扣（LeetCode）
其实这道题问题的就是有向图中是否有环。
我们可以把给的信息抽象称一张有向图，题目问能否完成所有课程学习意思就是能不能把这个课程排个序，说白了就是能否拓扑排序，能否拓扑排序也就是是否这个图是否是有向无环图 —> 有向图中是否有环？
做一次拓扑排序即可，前面已经说过如何拓扑排序，接下来重点就是如何建图？
如何建图？灵活使用语言提供的容器
看稠密（看数据量）
- 邻接矩阵（稠密图）
- 邻接表（稀疏图）
这道题我们用邻接表建图
相像中的邻接表最左边代表某个节点，这个节点右边一坨代表这个点所连接的点。
看起来就像一个个链表，头表示当前所考虑的这个节点，后面相连所有的节点是与我当前点相连的节点。我们建图的目的就是为了方便找到某个点所连接的那个点。不然还要遍历数组去找太麻烦了，所以把这些东西先存到一个数据结构中，这个数据结构就是图。
邻接表我们脑海中想到的应该就是这样的一条一条链表的结构。
那如何实现一个邻接表呢？
我们没有必须真的搞一个链表出来，这里有两种方式：
- vector<vector> edges
- unordered_map<int,vector> edges
用vector嵌套一个vector是比较局限的，只能用于节点里面的值是数字表示的。
用unordered_map是比较万能的，可以把int —> string， vector< int > —> vector< string >，等等其他任何类型。
vector嵌套一个vector，通过下标可以找到与这个节点的值相连的其他节点。仅需在对应下标的vector做push_back就可以把与当前节点相连的节点加入。
用unordered_map就比较万能了，完全像刚才想象出来的邻接表结构，我们这里是一个int的数后面挂了一个int数组，那不就和一个节点挂着一个节点的效果一样的吗。用数组表示所连接的节点。
- 根据算法流程，灵活建图
刚才我们只是实现把所有的边存起来。我们还要根据算法流程多添加一些东西。
比如这里我们是做拓扑排序，因此我们需要直到每个顶点的入度是多少。可以搞一个vector< int > in，数组里面的值就表示这个顶点的入度是多少。
总结：建图先看数据量选择邻接矩阵还是邻接表来建图，然后根据算法流程，灵活的在建图的基础上多添加上一点东西。
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
// 1. 准备工作
unordered_map<int,vector<int>> edges;//邻接表存图
vector<int> in(n);// 标记每一个顶点的入度
// 2. 建图
for(auto& e : prerequisites)
{
int a = e[0], b = e[1];// b -> a 的一条边
edges[b].push_back(a);// 把与b相连的顶点添加对应数组
in[a]++;// 记录对应顶点的入度
}
// 3. 拓扑排序
queue<int> q;
// (1) 把所有入度为 0 的顶点加入到队列中
for(int i = 0; i < n; ++i)
{
if(in[i] == 0)
q.push(i);
}
// (2) bfs
while(q.size())
{
int t = q.front();
q.pop();
//这道题没有让求顺序
//把与这个顶点相连的边干掉,就是修改与其相连顶点的入度
for(auto& a : edges[t])
{
in[a]--;//入度-1
if(in[a] == 0)//入度变为0加入队列
q.push(a);
}
}
// 4.判断是否有环
//如果整个拓扑排序结束之后,每个顶点的入度都变成0了说明没有环,否则就有环
for(int i = 0; i < n; ++i)
{
if(in[i]) return false;
}
return true;
}
};
题目二——210. 课程表 II - 力扣（LeetCode）
这道题和上面是一模一样的，还是做一次拓扑排序，不同的是这次要把拓扑排序顺序返回来。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int>in(numCourses,0);
unordered_map<int,vector<int>>end;
for(auto&tmp:prerequisites)
{
int a=tmp[0],b=tmp[1];
end[b].push_back(a);
in[a]++;
}
queue<int>q;
vector<int>ret;
for(int i=0;i<numCourses;i++)
{
if(in[i]==0)
{
q.push(i);
}
}
while(q.size())
{
int a=q.front();
q.pop();
ret.push_back(a);
for(auto&tmp:end[a])
{
in[tmp]--;
if(in[tmp]==0)
{
q.push(tmp);
}
}
}
if(ret.size()==numCourses) return ret;
else return {};
}
};
题目三——B3644 【模板】拓扑排序 / 家谱树 - 洛谷
从这道题目开始，我将使用算法竞赛里面拓扑排序常用的实现方式来做
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n;
vector<int>edges[N];
int in[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int j;
while(cin>>j&&j!=0)
{
edges[i].push_back(j);
in[j]++;
}
}
queue<int>q;
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
q.push(i);
}
}
while(q.size())
{
int t=q.front();
q.pop();
cout<<t<<" ";
for(auto&x:edges[t])
{
in[x]--;
if(in[x]==0)
{
q.push(x);
}
}
}
} 
题目四—— P2712 摄像头 - 洛谷
说实话，这题是使用拓扑排序来判断是否有环的问题。
#include<bits/stdc++.h>
using namespace std;
const int N=510;
vector<int>edges[N]; // 邻接表存储图结构
int in[N]; // 入度统计数组
bool st[N]; // 标记节点是否存在摄像头
int main()
{
int n;
cin>>n;
// 输入处理阶段
for(int i=1;i<=n;i++)
{
int x,m;
cin>>x>>m; // 当前节点编号x，有m个依赖
st[x]=true; // 标记该位置有摄像头
while(m--)
{
int t;cin>>t;
edges[x].push_back(t); // 添加x->t的边
in[t]++; // t节点的入度增加
}
}
// 拓扑排序初始化：找到初始入度为0的起点
queue<int>q;
for(int i=1;i<=500;i++) // 遍历所有可能的节点编号
{
// 只有存在摄像头且入度为0的节点才能作为起点
if(in[i]==0&&st[i])
{
q.push(i);
}
}
// 拓扑排序核心过程
while(q.size())
{
int t=q.front();q.pop();
// 遍历当前节点的所有后继节点
for(auto&x:edges[t])
{
in[x]--; // 移除当前节点后，后继节点入度减1
// 若入度归零且存在摄像头，则加入处理队列
if(in[x]==0&&st[x])
{
q.push(x);
}
}
}
// 统计结果阶段
int ret=0;
for(int i=0;i<=500;i++) // 注意这里包含i=0的检查
{
// 残留入度不为0的摄像头节点即为环路中的节点
if(in[i]!=0&&st[i])
{
ret++;
}
}
// 结果输出：无环路输出YES，否则输出环路节点数量
if(ret==0)
cout<<"YES"<<endl;
else
cout<<ret;
} 
题目五 ——P4017 最大食物链计数 - 洛谷
注意审题！题⽬问的是⼀共有多少条路径！
拓扑排序的过程中，进⾏动态规划。
对于每⼀个节点i，通过它的路径为：所有前驱结点的路径总数之和。
按照动态规划的思想就是dp[i]=dp[i-1]+nums[i]，那在拓扑排序里面我们怎么实现呢？
因此，可以在拓扑排序的过程 中，创建一个f[i]数组来维护从起点开始到达每⼀个节点的路径总数。
注意一个点：最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。
这说明我们的图应该是 被吃的东西->吃别人的东西
注意入度不要给错了。
#include<bits/stdc++.h>
using namespace std;
const int N=5010,MOD=80112002;
vector<int>edges[N];
int in[N];
int dp[N];
int out[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
edges[x].push_back(y);
in[y]++;
out[x]++;
}
queue<int>q;
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
dp[i]=1;
q.push(i);
}
}
while(q.size())
{
int t=q.front();
q.pop();
for(auto&x:edges[t])
{
dp[x]=(dp[x]+dp[t])%MOD;
in[x]--;
if(in[x]==0)
{
q.push(x);
}
}
}
int ret=0;
for(int i=1;i<=n;i++)
{
if(out[i]==0)
{
ret=(ret+dp[i])%MOD;
}
}
cout<<ret<<endl;
}
题目六——P1113 杂务 - 洛谷
拓扑排序的过程中，进⾏动态规划。
对于每⼀个事件i ，完成它的最⼩时间为：完成前驱所有事件的最⼩时间中的最⼤值+当前事件的完 成时间。
注意：有足够多的工人这一条件
因此，可以在拓扑排序的过程中，维护每⼀个事件完成的最⼩时间，然后更新当前事件的最 ⼩时间。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 10010;
int n;
vector<int> edges[N];
int in[N], f[N];
int len[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int b, a;
cin >> b >> len[b];
while (cin >> a, a)
{
edges[a].push_back(b);
in[b]++;
}
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (in[i] == 0) q.push(i);
}
int ret = 0;
while (q.size())
{
int a = q.front(); q.pop();
f[a] += len[a];
ret = max(ret, f[a]);
for (auto b : edges[a])
{
f[b] = max(f[b], f[a]);
in[b]--;
if (in[b] == 0) q.push(b);
}
}
cout << ret << endl;
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
25
0- 0
已为社区贡献10条内容
所有评论(0)