图论——拓扑排序

• 拓扑排序模板
• 拓扑排序判环
• 关键路径

拓扑排序模板

拓扑排序是由队列实现的

拓扑排序不是按大小来排序的，是根据先后关系来排序的，由入度为零的点进队开始，删除此点所有出度的边，到最后找完所有点即可，拓扑排序不是只有唯一的序列，可能会有多组拓扑序列；

代码

本人是用数组模拟队列来实现的，也可以使用queue，c++自带队列来实现。

拓扑排序判环

因为拓扑序列有一个性质就是从入度为零的点开始排序，如果图中有环，说明环中的点每个都不是入度为零的点，每个都遍历不到，根据这个性质就可以来判断图中是否有环。如果拓扑序列不够n个，则说明图中有环。

代码

sum存的就是拓扑序列的个数，如果等于n证明图中没有环

关键路径

这个知识点我第一开始没有看懂，不知道到底是什么意思，老师解释了一下才明白，打个比方，现在有一个工程，最长路就是关键路径，影响工程的进度的活动叫做关键活动，在关键路径上的活动一定是关键活动。

这个主要就是求一个最长路，本人认为有DP的味道，在此代码就不给了，因为这种对应的题型都不一样，并没有通用模板。