数据结构之图的拓扑排序_在拓扑排序序列中任意两个相继

我是自动化专业的应届研究生，最终拿到了tplink、华为、vivo等公司的ssp的offer，分享自己学习过的计算机基础知识（C语言+操作系统+计算机网络+linux）以及数据结构与算法的相关知识，保证看完让你有所成长。
欢迎关注我，学习资料免费分享给你哦！还有其他超多学习资源，都是我自己学习过的，经过过滤之后的资源，免去你还在因为拥有大量资源不知如何入手的纠结，让你体系化学习。

什么是拓扑排序

拓扑排序就是任务之间有先后依赖关系，在完成一项任务之前必须完成某一项或者某几项任务，才可以完成它。比如大学的排课，都是将基础的微积分与线性代数放在第一个学年，学会这些基础之后，才可以学习复变函数，电路，大学物理等。就是对于这些有依赖关系的项目之间的排序就是拓扑排序。比如某个专业有20门课，某些课之间存在依赖关系，这些关系已知，那么如何排课呢？就是每个学期应该哪几门课？这就是拓扑排序的用处。

拓扑排序的基本思路

假设有10门课，分别以C1到C10表示。

可以把每门课程看成是一个顶点，先修课程与课程之间就可以是图中的一条有向边了，根据这种表示，可以将上面的表转换为数据结构中的图。

如图所示，可以看到各门课程的依赖关系，那么如何实现排课，也就是拓扑排序呢？这要依靠图的一个概念——入度，什么是入度，就是在有向图中，从别的顶点指向自己本身的边的个数，如图中C2，入度就为1，因为只有一个边指向它，还有一个出度的概念，就是从这个顶点出发的边的个数，C2的出度也为1。C9的入度为2，出度为1。那么如何把顶点的入度与拓扑排序结合呢？我们排课不就是将没有预设课程的课程先排上，然后在逐层向下嘛，那么在图中，就是入度为0的顶点就是代表着没有预设课程的课程，所以只要扫描图，然后将入度为0的课程选出来，将其指向的课程的入度减1，就可以了，直到所有课程都排好。来具体分析一下整个过程。

首先假设从C1开始，将C1拿出来，然后将C2的入度减1，得到下面所示的图

然后继续扫描图，C3的入度为0，将C3排到课程中，C4的入度减1。

继续将入度为0的C7排到课表，将C9的入度减1。

就这样层层的递减，每一次都将入度为0的顶点排序，将其指向顶点的入度减1，直到图中的所有顶点都已经排序，这样就得到了拓扑排序的结果。当然拓扑排序的结果不唯一。比如上面在C1排序之后，面对C2，C3,C7,C8的入度均为0，你取出的顺序不同，排序的结果就不同了。按照我们上面的排序结果如图所示：

我们根据前面的描述可以得出如下的伪代码