如果只需要判断是否有环，一般有两种方法

拓扑排序

一般为人熟知的为 kahn 算法，稍微做一些改变

  1. 计算所有节点的入度，
  2. 找到所有入度为 0 的点，并记录下入度为 1 的后驱点
  3. 删除入度为 0 的点，同时删除以它们为起始的边，这时后驱点入度变为 0
  4. 重复 2-3 步骤，直到没有入度为 0 的点，假如图中还存在顶点，则图中存在环

优点：算法简洁，容易理解和实现 缺点：剩余的节点并不一定全都是环中的节点，而且并不能将所有环直观地输出

深度遍历 DFS

我们总共需要两个辅助数据

  1. 记录所有已经访问过的点的状态
  2. 从出发节点到当前节点的轨迹

我们将节点分为三种状态，白，灰，黑。开始的时候所有的节点都是白色，当开始访问某个节点的时候，节点变为灰色，当该节点的所有后驱点都访问完了，节点颜色变为黑色。

当我们在遍历的过程中发现某个节点的一条边指向了一个灰色的节点，则存在环

这种方式能将所有的环都找出来，比较通用

强连通分量

图论中，强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。意即对于此图上每一个点对(Va,Vb)，皆存在路径 Va→Vb 以及 Vb→Va。强连通分量则是指一张有向图 G 的极大强连通子图 G'。如果将每一个强连通分量缩成一个点，则原图 G 将会变成一张有向无环图。一张图被称为有向无环图当且仅当此图不具有点集合数量大于一的强连通分量，因为有向环即是一个强连通分量，而且任何的强连通分量皆具有至少一个有向环。

Tarjan 算法