算法妙招！有向图检测是否存在环？_有向图成环检测

由于细节内容实在太多啦，所以只把部分知识点整理出来粗略的介绍，每个小节点里面都有更细化的内容！ 

接下来开始分享啦 

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

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

拓扑排序的一般流程：

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

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

3.更新出度。

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

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

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

表有出度的有向图

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