5
第5-2课：图的拓扑排序
source link: https://blog.csdn.net/orbit/article/details/108729352
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
拓扑排序常用来确定一个依赖关系集中、事物发生的顺序。一个典型的应用场景就是在项目管理或工程实施中安排各种生产活动的计划，在考虑各种活动的依赖关系的基础上，安排各种活动的开始时间，使得项目或工程能够以高效合理的速度完成。这些功能通常需要在基本的拓扑排序算法基础上进行适当的改造，本课仿照的项目管理软件功能实现的“根据活动开始时间排序”算法，就是一种这样的改造。图的拓扑排序涉及的概念有：有向无环图（Directed Acyclic Graph，DAG）、AOV 网、顶点的出度和入度等。在学习这一课的内容之前，希望大家对这些概念能有一些了解，好了，废话不多说，开始吧。
拓扑排序（Topological Sorting）
对有向无环图进行拓扑排序，是图论算法中的一个重要算法，它不仅是各种算法题目中常见的内容，在现实生活中也得到了广泛的应用，比如各种项目管理软件中的“按照开始时间排序”功能，其背后的算法支撑就是拓扑排序。这一课，我们用一个简化的工程活动安排这个题目为例，介绍一下拓扑排序算法的应用。
假如某工程分解后得到 P1 ~ P9 共 9 个活动，这些活动需要的时间和它们之间的依赖关系如下表所示：
活动名称
活动时间（天）
前置依赖
P1
8
P2
5
P3
6
P1、P2
P4
4
P3<
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK