基于DFS的环检测算法 题目描述 给定一个有向图，判断图中是否存在环。如果存在环，请找出图中所有的环。这个问题在图论中非常重要，因为许多应用（如任务调度、依赖关系分析）都要求图是无环的（即一个DAG，有向无环图）。 解题过程 环检测的核心思想是追踪当前DFS遍历路径上的节点。如果在遍历过程中，我们遇到了一个已经在当前路径上的节点，那么就发现了一个环。 我们将使用深度优先搜索（DFS）和三种颜色标记法来追踪节点的状态： 白色 ：节点尚未被访问。 灰色 ：节点已被访问，但其DFS递归调用尚未结束。这个节点位于当前DFS遍历的路径（栈）上。 黑色 ：节点的DFS递归调用已结束。这个节点及其所有后代都已被完全处理。 算法步骤 初始化 ： 创建一个字典（或数组） color ，用于记录每个节点的颜色。初始时，所有节点都被标记为白色。 创建一个字典（或数组） parent ，用于记录在DFS树中每个节点的前驱节点（即是从哪个节点遍历到它的）。这有助于在发现环时回溯整个环的路径。 （可选）创建一个集合或列表，用于存储找到的所有环。 DFS遍历 ： 遍历图中的每一个节点。 如果当前节点 u 是白色的（未访问），则调用 DFS-Visit(u) 函数。 DFS-Visit(u) 函数 ： 将节点 u 的颜色标记为灰色，表示我们开始访问它。 遍历节点 u 的所有邻居节点 v ： 如果邻居 v 是白色的（未访问）： 将 v 的父节点设置为 u ( parent[v] = u )。 递归调用 DFS-Visit(v) 。 关键情况 ：如果邻居 v 是灰色的（已访问且在当前DFS路径上）： 这说明我们找到了一条从 u 回到 v 的边，而 v 还在当前的递归栈中。这意味着我们发现了一个环！ 此时，我们可以通过 parent 字典从 u 开始向上回溯，直到回溯到 v ，这条路径就构成了一个环。将这个环记录下来。 如果邻居 v 是黑色的（已访问且已处理完毕），则忽略。这意味着从 u 到 v 的边可能是一条交叉边或前向边，不会构成环（在DFS树中）。 在遍历完 u 的所有邻居后，将 u 的颜色标记为黑色，表示以 u 为根的子树已处理完毕。函数返回。 输出结果 ： 如果算法执行完毕后，记录环的集合为空，则说明图中无环。 否则，输出集合中记录的所有环。 举例说明 考虑一个有向图：节点集合为 {A, B, C, D}，边集合为 {A->B, B->C, C->A, C->D}。 初始化所有节点为白色。 从节点A开始DFS： 将A标记为灰色。 访问A的邻居B（白色），递归进入B。 处理节点B： 将B标记为灰色。 访问B的邻居C（白色），递归进入C。 处理节点C： 将C标记为灰色。 访问C的邻居A：发现A是灰色的（A->B->C，A还在当前路径上）！ 发现环 ！ 回溯环路径：C的父节点是B，B的父节点是A，A就是环的起点。所以环是 A -> B -> C -> A。 继续访问C的邻居D（白色），递归进入D。 处理节点D： 将D标记为灰色。 D没有出边，将其标记为黑色，返回。 回溯到C：C的所有邻居处理完毕，将C标记为黑色，返回。 回溯到B：B的所有邻居处理完毕，将B标记为黑色，返回。 回溯到A：A的所有邻居处理完毕，将A标记为黑色，返回。 算法结束。我们找到了一个环：A->B->C->A。 关键点 只有遇到 回边 （指向当前DFS路径上某个灰色节点的边）时，才会形成环。 黑色节点意味着该节点的所有后代都被探索过，从当前节点到黑色节点的边不会构成环。 这个算法的时间复杂度是 O(V+E)，其中V是顶点数，E是边数，与DFS的复杂度相同。