# 拓扑排序

## 拓扑排序

**拓扑排序** ，用来获得一个 **有向无环图（DAG）** 的所有顶点的线性序列。

该序列满足两个条件：

* 每个顶点只出现一次。
* 若存在一条从顶点`A`到顶点`B`的路径，那么在序列中，顶点`A`出现在顶点`B`前面。

## `Kahn`算法

定义数据结构时，如果顶点`s`排在`t`前面，那就添加一条`s`指向`t`的边。

所以，如果某个顶点的入度为0，那就表示没有任何顶点排在它前面，这个顶点就可以取出来。

**算法思想：**

* 使用临接表表示图，并定义数据结构记录每个顶点的入度。
* 先找到入度为0的点，将其输出。
* 把这个顶点从图中删除，并且这个顶点可达的所有顶点入度都减一。
* 重复上述步骤，直到所有顶点都输出。最后输出序列就是满足依赖关系的拓扑排序。

## 深度优先遍历

**算法思想：**

* 通过邻接表构造逆邻接表。
* 递归处理每个顶点。先依次输出它依赖的所有顶点，再输出自己。
* 可以根据访问记录，判断是否出现环。
