基于DFS的环检测算法

题目描述
给定一个有向图（或无向图），判断图中是否存在环。若存在环，则返回True；否则返回False。环检测在任务调度、死锁检测等场景有重要应用。

解题过程

1. 问题分析

• 有向图：存在环的条件是图中存在一条路径，使得起点和终点相同，且路径长度至少为1（自环或多节点环）。
• 无向图：环的定义类似，但需注意无向图中相邻节点的双向边不构成环（需要至少3个节点）。
• 核心思路：通过遍历图（如DFS）记录当前路径上的节点，若遇到已访问且在当前路径中的节点，则存在环。

2. 算法选择：基于DFS的环检测

有向图环检测步骤

1. 标记状态：为每个节点定义三种状态：
   • 未访问（0）：节点尚未被处理。
   • 访问中（1）：节点在当前的DFS递归栈中（即正在探索其邻居）。
   • 已访问（2）：节点及其所有邻居已被处理完毕。
2. DFS遍历：
   • 从任意未访问节点启动DFS。
   • 对于当前节点u，将其状态设为“访问中”。
   • 遍历u的邻居v：
     • 若v为“未访问”，递归检查v。
     • 若v为“访问中”，说明存在环（因为v在当前路径中）。
   • 完成u的所有邻居遍历后，将其状态设为“已访问”。
3. 复杂度：时间复杂度为O(V+E)，空间复杂度为O(V)（递归栈或显式栈）。

无向图环检测步骤

1. 避免重复访问：记录每个节点的父节点（即从哪个节点访问到当前节点），防止将父节点误判为环。
2. DFS遍历：
   • 从任意未访问节点启动DFS。
   • 对于当前节点u，标记为已访问。
   • 遍历u的邻居v：
     • 若v未被访问，递归检查v，并记录u为v的父节点。
     • 若v已被访问且v不是u的父节点，说明存在环（因为u和v通过另一条路径连接）。

3. 示例演示

有向图示例

图：0→1→2→0（三角形环）

• 从节点0开始DFS：
  • 0状态变为“访问中”，进入邻居1。
  • 1状态变为“访问中”，进入邻居2。
  • 2状态变为“访问中”，进入邻居0。
  • 0已是“访问中”，检测到环！

无向图示例

图：0-1-2-0（三角形环）

• 从节点0开始DFS：
  • 访问1（父节点为0），再访问2（父节点为1）。
  • 2的邻居0已被访问，且0不是2的父节点（2的父节点是1），检测到环！

4. 代码框架（有向图）

def is_cyclic_directed(graph):
    state = {node: 0 for node in graph}  # 0=未访问, 1=访问中, 2=已访问
    
    def dfs(u):
        state[u] = 1  # 标记为访问中
        for v in graph[u]:
            if state[v] == 0:  # 未访问节点
                if dfs(v):
                    return True
            elif state[v] == 1:  # 遇到当前路径中的节点
                return True
        state[u] = 2  # 标记为已访问
        return False
    
    for node in graph:
        if state[node] == 0:
            if dfs(node):
                return True
    return False

5. 关键点总结

• 有向图：需区分“访问中”和“已访问”状态，仅当邻居为“访问中”时才判定为环。
• 无向图：需记录父节点避免误判，且环至少需要3个节点。
• 应用扩展：可修改算法记录环的具体路径，或用于拓扑排序（无环有向图才有拓扑序）。