八十六、从拓扑排序探究有向图

@Author：Runsen

关于排序，其实还有很多，比如常见的希尔排序，桶排序，计数排序和基数排序，由于要过渡到数据结构有向图，因此需要了解拓扑排序和邻接矩阵概念。

拓扑排序

拓扑排序本身并不是一个排序，排序是指一个数组数据，而且数据之间是没有任何联系的。

拓扑排序是从拓扑学引出来的概念，所谓的拓扑学(Topology)，是一门研究拓扑空间的学科，主要研究空间内，在连续变化（如拉伸或弯曲，但不包括撕开或粘合）下维持不变的性质。其实我也是一个半懂又不是很懂得状态。

下面先来看一个生活中的拓扑排序的例子，例子来源王争的算法专栏。

我们在穿衣服的时候都有一定的顺序，我们可以把这种顺序想成，衣服与衣服之间有一定的依赖关系。比如说，你必须先穿袜子才能穿鞋，先穿内裤才能穿秋裤。

假设我们现在有八件衣服要穿，它们之间的两两依赖关系我们已经很清楚了，那如何安排一个穿衣序列，能够满足所有的两两之间的依赖关系？

拓扑排序的原理非常简单，下面是一个牛客关于拓扑排序的选择题，好像是2017滴滴校招的笔试题，其实就是送分题。

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/111771458