算法：有向图检测_有向图找环算法

有向图检测是否存在换是比较常见的场景。在一些调度引擎中，调度的任务往往存在依赖，而检测是否存在循环依赖，即有向图中是否存在环是调度引擎的职责。当然，也是面试中常遇到的算法。今天为大家介绍用拓扑排序方法检测有向图中是否有环。

出度和入度的概念。一张有向图是有顶点和带有方向的边组成的。对于一个顶点，如果有n边从其他顶点指向此顶点，则这个顶点的入度就是n。相应的，如果有n条边从这个顶点指向其他顶点，则这个顶点的出度就是n。

拓扑排序的一般流程：

1.初始化各个顶点的出度（或者入度也行，本文以出度为例）。

2.移除出度为0的顶点和与此顶点相连的边。

3.更新出度。

4.重复步骤2和3，直到不存在出度为0的顶点或者顶点已经全部被移除了。

5.判断是否存在剩余顶点，存在和存在环，不存在，则无环。

例：下图是一个6顶点的有向图，其中每个顶点的出度，已经用红色的数字标在了顶点旁边。

表有出度的有向图

在移除出度为0的顶点之后，更新出度。此时如下图：

更新后的有向图

图中已经没有出度为0的顶点了，不能再移除了。现在还剩下一些顶点，由此可以判断这个有向图是存在环的。

代