判断有向图是否有环

计算机软件开发 · 2024-9-21 22:11:28

题目泉源于做题力扣-顺丰科技聪明物流校园技术挑衅赛中的第一题。
没阅读《剑指Offer》之前看到题时不会做，在阅读过程中有本身的解题想法，也看到《剑指Offer》中提到的解法。先按本身的想法实现，效果发现了本身想法的误区，以是在这里记载一下误区及缘故起因，以及正确的解法。
如下图，红线为故意加入的一个导致有向图中形成环。
入度和出度

入度统计的是有多少箭头指向本身。
出度统计的是本身有多少箭头指向别人。

如上图中节点 8 被两个箭头指向，以是它的入度为 2；有一个指向 12 的箭头，以是出度为 1。同理，上图节点 5入度为 1，出度为 2。
错误的想法

思量到有环，以是直观的想法是：沿着路走，如果某条路不停导致重复走某些节点，那么就证明存在环。
细节：

怎么沿着路走：用广度优先算法（队列）。可以。
怎么确定有环的详细条件：Em...（支支吾吾）根据...入度次数？

题目就出在判断有环的条件上，你不好判断某几个点是不停在循环。思量如下几点：

如果 A 点到 B 点的路径有 3 中，B 到 C 的路径有 5 种，那么 A 到 C 一共有 15 种路径。如果广度优先算法中不限定访问过的点再次访问，那么从到 C 点就至少有 15 种走法。怎样定上限就是个题目。
上步中，如果要限定每个点都被走一次也不能判断有环。非常地例子如 A 能走向 B 和 C，B 能走向 C，C 也能走向 B，怎么判断这种环？
那统计边的次数呢？……

思量边是正确的想法。但怎样判断有环条件还必要进一步思量细节：

规定每个边只走一次？每个边都会走到。单纯这个条件没法判断
规定每个边只走一次，再加上每个点只走一次呢？也不可，思考一下可以知道点上不能限定只走一次。
规定每个边只走一次，每个点上只走它的入度次？这个好像可以。验证一下好像还少个 “没有路时是否为尽头” 的条件。
规定每个边只走一次，每个点上只走它的入度次，且末了无路时总是走向尽头。若不是尽头，则证明有环。哎，这个好像可以。

但上方末了一个方案照旧有题目标：没有思量 “孤岛” 的存在，如只有一个 A 节点没有入度也没有出度，或 A、B 节点相互有向毗连。如果加逻辑判断又该怎么加呢？
此时已经差不多很靠近正确的解法了，详细参考下节吧。
正确的解法

《剑指Offer-专项突击版》在图-拓扑排序一节中有提到解法。文中重要讲的是拓扑排序，我这里转化一下针对于查环形貌：
每次从有向图中取出一个入度为 0 的节点删除，同时删除该节点及全部以他为出发点的边，若终极图为空则证明无环，终极非空则证明有环。

原文：“一种常用的拓扑排序算法是每次从有向无环图中取出一个入度为 0 的节点添加到拓扑排序序列之中，然后删除该节点及全部以它为出发点的边。重复这个步调，直到图为空或图中不存在入度为 0 的节点。如果终极图为空，那么图是有向无环图，此时就找到了该图的一个拓扑排序序列。如果终极图不为空而且已经不存在入度为 0 的节点，那么图中肯定有环。”

为什么呢？：我们来单独思量一个单环，那么环中每一个点都是入度为 1，出度也为 1，即不大概入度为 0。按上面删环的形貌过程，如果环存在，这个环中的的每个点都无法偶然机酿成入度为 0 的点，因此就证明白环的存在。

哈，类似于环中象棋中的“连环马”战术了：每个节点相互看管。“入度为 0”这只矛根本无从动手（无法入环）。

解题思绪及代码

力扣-顺丰科技聪明物流校园技术挑衅赛。
解题思绪

团体思绪：通过每次删除入度为 0 的边，末了判断是否尚有删除不到的边存在。删除不到就是由于不存在入度 0 的边了。若存在就是有环，否则无环。
细节：

用边的聚集来体现此图，由于要有删除边的使用。
要记载全部点的入度，以是用个 map 记载入度（inCounts）
要查找下一个节点，以是要用个 map 记载路径的两点
入度为 0 的点是要分析的点，以是用个队列记载全部入度为 0 的点（heads）

综上：每次通过入度为 0 的 heads 数组中取一个，遍历它的下一个节点 target，删除此路 edge，并更新 target 的入度（减一），若 target 入度为 0，加入到 heads 中，以备下次分析到。
解题代码

目前只记载了个人从书上得到的解法及本身写的思绪。还必要看看书中是不是有其他细节的有环，或其他人的代码的方法。（力扣上用 dfs 遍历看一下）

判断有向图是否有环

所属分类: 问答交流

新帖推荐: 30日

推荐作品