算法：有向图检测是否存在环

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

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

拓扑排序的一般流程：

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

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

3.更新出度。

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

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

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

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

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

代码实现：

为了表达算法的整体思想，仅保留了部分关键代码。图有很多中表示方式，在本例中，使用顶点的集合和边的集合来表示。对于其他的表示方式，读者可以自己去尝试实现此算法。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

关注下方微信公众号：java圈子，获取价值999元全套java入门到进阶的学习资料以及教程，还有java技术交流群一起交流学习哦。

0 条评论