前言

对于一个有向无环图（DAG），求拓扑排序最常见的方法:

① 从DAG图中选择入度为0的顶点，并输出。

② 从图中删除该入度为0的顶点及所有以它为起点的边。

③ 重复（1）和（2）直到当前图为空，或者图不存在入度为0的顶点。前者输出的序列就是拓扑排序；后者说明图中有环，不存在拓扑序列。

所以当需要判断某个图是否有环时，都应立刻想到求拓扑序列。

 

例题