填坑——拓扑排序

    拓扑排序很早以前就接触过了，大概是在本科二年级的时候，然鹅现在已经研三了，过去太久了，所以只对这个名词挺熟悉，对它的算法都忘的差不多了，但是昨天面试的腾讯实习，面试官突然问到这个问题，面试之前还是复习过十大经典排序算法，可是拓扑排序确实没有复习过，所以现在决定填坑。把拓扑排序的知识点补起来。

    首先，拓扑排序并非真的排序，这一点是基础，当时我被问到拓扑排序的时候第一个想到的就是排序，但是当时复习的十大排序算法中并没有拓扑排序，从而导致面试的时候进一步的慌张。下面是拓扑排序的百度词条定义。

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

    简而言之就是要将有向图的顶点（图结构的）变成线性结构的，怎么变的呢？它有一个规则，从一个入度为0的顶点开始遍历，遍历过后，从图中删除该顶点以及它所对应的出边，循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

如下图，拓扑排序过程如下：