拓扑排序检测有向图中的环核心依据是一个有向图能进行拓扑排序当且仅当它是有向无环图DAG。因此如果拓扑排序无法处理完所有顶点就说明图中存在环。[适用范围]拓扑排序只能处理 DAG如果排序结果覆盖不了全部顶点剩下的顶点就处在环中。1. Kahn 算法基于入度Kahn 算法的思路1. 统计每个顶点的入度。2. 把所有入度为 0 的顶点加入队列。3. 每次从队列取出一个顶点加入拓扑序列。4. 删除该顶点及其所有出边· 对它的每个邻接点入度减 1· 如果某个邻接点入度变成 0就加入队列。5. 重复直到队列为空。6. 最后判断· 如果拓扑序列中的顶点数等于图中总顶点数说明无环· 如果少于总顶点数说明存在环。为什么能检测环如果图中存在环例如A → B → C → A这个环中每个顶点都至少有一条来自环内其他顶点的入边所以它们的入度不可能变成 0。当所有不在环上的顶点被处理完后环上的顶点仍然互相依赖入度始终大于 0无法进入队列。于是最终已处理顶点数 总顶点数剩余未处理的顶点一定构成环或包含环。2.举例说明拓扑排序要求如果存在边 u → v那么 u 必须排在 v 前面。但在环中A → B → C → A会推出· A 必须在 B 前· B 必须在 C 前· C 必须在 A 前。这就产生矛盾A B C A不可能同时成立。所以只要存在环就不存在合法的拓扑排序。3. DFS 方法基于递归栈另一种检测环的方法是 DFS 三色标记· 白色未访问· 灰色正在当前递归路径中· 黑色已访问完成。DFS 时如果遇到一个灰色节点说明当前路径回到了自己存在环。原理是灰色节点表示它还在当前 DFS 递归栈中。如果从某个节点又能走到它说明形成了一条后向边也就是环。4. 总结拓扑排序检测环的原理可以概括为1. 有向图无环时一定存在至少一个入度为 0 的起点。2. 不断删除入度为 0 的节点及其出边可以逐步剥去无环部分。3. 如果图中存在环环内节点互相提供入度无法被剥掉。4. 因此若最终无法处理所有节点就说明存在环。小记面对遗漏笔记的态度他被放在了一个他会想到的复习无法找到地方。这也就是我们做笔记需要考虑的一个点其实应该考虑到复习能否找到。这里就对呃曾经做过的笔记但是找不到做一个补充。