判斷有向圖是否存在環路：Kahn 拓撲排序與 DFS 兩大經典算法

給定有向圖的邊列表 (而非鄰接矩陣)，判斷是否存在環路是圖論基礎問題。本文提供 **Kahn 算法 (BFS 拓撲排序)** 與 **DFS 遞歸** 兩種主流解法，並給出 Java 與 C# 完整實現。

核心思想

• Kahn 算法：不斷刪除入度為 0 的節點。若最終刪除的節點數 < 總節點數，則存在環。
• DFS 顏色標記：白(未訪問)、灰(正在訪問/遞歸棧中)、黑(訪問完成)。若 DFS 過程遇到灰色節點，即發現回邊 → 有環。

數據結構：鄰接表 (邊列表 → 鄰接表)

無論哪種語言，第一步都是將邊列表轉為鄰接表：

// Java
Map> graph = new HashMap<>();
for (int[] edge : edges) {
    graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
    // 確保目標節點也在 map 中 (即使無出邊)
    graph.putIfAbsent(edge[1], new ArrayList<>());
}

方案一：Kahn 算法 (BFS) — 推薦，無遞歸棧溢出風險

Java 實現

public boolean hasCycleKahn(int[][] edges) {
    Map> graph = new HashMap<>();
    Map inDegree = new HashMap<>();

    // 建圖 & 計算入度
    for (int[] e : edges) {
        graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        inDegree.put(e[1], inDegree.getOrDefault(e[1], 0) + 1);
        inDegree.putIfAbsent(e[0], 0); // 確保源節點在 map 中
    }

    Queue q = new LinkedList<>();
    inDegree.forEach((node, deg) -> { if (deg == 0) q.offer(node); });

    int visited = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        visited++;
        for (int v : graph.getOrDefault(u, Collections.emptyList())) {
            if (--inDegree.get(v) == 0) q.offer(v);
        }
    }
    return visited != inDegree.size(); // 有環
}

C# 實現

public bool HasCycleKahn(int[][] edges) {
    var graph = new Dictionary>();
    var inDegree = new Dictionary();

    foreach (var e in edges) {
        if (!graph.ContainsKey(e[0])) graph[e[0]] = new List();
        graph[e[0]].Add(e[1]);
        inDegree[e[1]] = inDegree.GetValueOrDefault(e[1], 0) + 1;
        if (!inDegree.ContainsKey(e[0])) inDegree[e[0]] = 0;
    }

    var q = new Queue(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key));
    int visited = 0;
    while (q.Count > 0) {
        int u = q.Dequeue();
        visited++;
        if (graph.TryGetValue(u, out var neighbors)) {
            foreach (int v in neighbors) {
                if (--inDegree[v] == 0) q.Enqueue(v);
            }
        }
    }
    return visited != inDegree.Count;
}

方案二：DFS 遞歸 (代碼更簡潔，適合節點數較小)

Java 實現

public boolean hasCycleDFS(int[][] edges) {
    Map> graph = new HashMap<>();
    for (int[] e : edges) {
        graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        graph.putIfAbsent(e[1], new ArrayList<>());
    }

    Map state = new HashMap<>(); // 0=白, 1=灰, 2=黑
    for (int node : graph.keySet()) {
        if (state.getOrDefault(node, 0) == 0 && dfs(node, graph, state))
            return true; // 發現環
    }
    return false;
}

private boolean dfs(int u, Map> graph, Map state) {
    state.put(u, 1); // 灰
    for (int v : graph.get(u)) {
        int s = state.getOrDefault(v, 0);
        if (s == 1) return true; // 回邊 → 環
        if (s == 0 && dfs(v, graph, state)) return true;
    }
    state.put(u, 2); // 黑
    return false;
}

C# 實現

public bool HasCycleDFS(int[][] edges) {
    var graph = new Dictionary>();
    foreach (var e in edges) {
        if (!graph.ContainsKey(e[0])) graph[e[0]] = new List();
        graph[e[0]].Add(e[1]);
        if (!graph.ContainsKey(e[1])) graph[e[1]] = new List();
    }

    var state = new Dictionary(); // 0=白, 1=灰, 2=黑
    foreach (var node in graph.Keys) {
        if (state.GetValueOrDefault(node, 0) == 0 && Dfs(node, graph, state))
            return true;
    }
    return false;
}

private bool Dfs(int u, Dictionary> graph, Dictionary state) {
    state[u] = 1;
    foreach (int v in graph[u]) {
        int s = state.GetValueOrDefault(v, 0);
        if (s == 1) return true;
        if (s == 0 && Dfs(v, graph, state)) return true;
    }
    state[u] = 2;
    return false;
}

複雜度對比與選型建議

建議：通用場景首選 **Kahn 算法**；節點數 < 10⁴ 且代碼簡潔優先時用 DFS。兩者均能直接處理「邊列表」輸入，無需轉鄰接矩陣。

擴展：輸出具體環路路徑

若需找出具體環，DFS 中維護 `parent` 映射，發現回邊時回溯即可；Kahn 算法則需結合 Tarjan 強連通分量算法。