06_Cycle Detection in Directed Graph 有向图环检测

有向图中的环检测

在有向图中检测是否存在环（Cycle）是一个经典问题。环是指从某个节点出发，沿着有向边最终能回到该节点的路径。

---

方法一：DFS + 三色标记

算法思想

使用三种颜色标记节点的状态： - 白色 (0)：未访问 - 灰色 (1)：正在访问（在当前递归栈中） - 黑色 (2)：已访问完成（不在递归栈中）

如果在 DFS 过程中遇到灰色节点，说明找到了环。

为什么有效？

• 灰色节点表示当前路径上的节点
• 如果再次遇到灰色节点，说明从该节点出发有一条边能回到当前路径
• 这就形成了一个环

代码实现

def has_cycle_dfs(n, graph):
    state = [0] * n   # 0未访问，1访问中，2已完成
    
    def dfs(node):
        state[node] = 1
        for nei in graph[node]:
            if state[nei] == 1:      # 遇到还在递归栈中的节点
                return True
            if state[nei] == 0:
                if dfs(nei):
                    return True
        state[node] = 2
        return False
        
    for node in graph:
        if state[node] == 0:
            if dfs(node):
                return True
    return False

时间复杂度

• 时间：$O(V + E)$，每个节点和边访问一次
• 空间：$O(V)$，存储颜色数组和递归栈

---

方法二：拓扑排序（Kahn 算法）

算法思想

1. 计算所有节点的入度
2. 将入度为 0 的节点加入队列
3. 不断从队列取出节点，将其邻居的入度减 1
4. 如果邻居入度变为 0，加入队列
5. 如果处理的节点数 < 总节点数，说明存在环

为什么有效？

• 有向无环图（DAG）至少存在一个入度为 0 的节点
• 如果有环，环内所有节点的入度都至少为 1
• 这些节点永远不会被加入队列

代码实现

from collections import deque

def has_cycle_topological(n, adj):
    """
    使用拓扑排序检测有向图中的环
    
    Args:
        n: 节点数量
        adj: 邻接表 adj[u] 表示从 u 能到达的所有节点
    
    Returns:
        bool: 是否存在环
    """
    # 计算入度
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]:
            in_degree[v] += 1
    
    # 将入度为 0 的节点加入队列
    q = deque([i for i in range(n) if in_degree[i] == 0])
    
    # 计数已处理的节点
    count = 0
    
    while q:
        u = q.popleft()
        count += 1
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    
    # 如果处理的节点数 < 总节点数，说明存在环
    return count < n


# 示例用法
if __name__ == "__main__":
    # 有环的图: 0 -> 1 -> 2 -> 0
    n1 = 3
    adj1 = [[1], [2], [0]]
    print(has_cycle_topological(n1, adj1))  # True
    
    # 无环的图: 0 -> 1 -> 2
    n2 = 3
    adj2 = [[1], [2], []]
    print(has_cycle_topological(n2, adj2))  # False

时间复杂度

• 时间：$O(V + E)$
• 空间：$O(V)$，存储入度和队列

---

两种方法对比

方法	优点	缺点	适用场景
DFS + 三色标记	代码简洁，递归自然	可能栈溢出	需要找到具体环的节点
拓扑排序	迭代实现，无栈溢出风险	需要额外计算入度	只需判断是否有环