拓扑排序

拓扑排序

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

该序列满足两个条件：

• 每个顶点只出现一次。

• 若存在一条从顶点A到顶点B的路径，那么在序列中，顶点A出现在顶点B前面。

Kahn算法

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

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

算法思想：

• 使用临接表表示图，并定义数据结构记录每个顶点的入度。

• 先找到入度为0的点，将其输出。

• 把这个顶点从图中删除，并且这个顶点可达的所有顶点入度都减一。

• 重复上述步骤，直到所有顶点都输出。最后输出序列就是满足依赖关系的拓扑排序。

深度优先遍历

算法思想：

• 通过邻接表构造逆邻接表。

• 递归处理每个顶点。先依次输出它依赖的所有顶点，再输出自己。

• 可以根据访问记录，判断是否出现环。