👋 大家好，欢迎来到我的技术博客！
💻 作为一名热爱 Java 与软件开发的程序员，我始终相信：清晰的逻辑 + 持续的积累 = 稳健的成长。
📚 在这里，我会分享学习笔记、实战经验与技术思考，力求用简单的方式讲清楚复杂的问题。
🎯 本文将围绕数据结构与算法这个话题展开，希望能为你带来一些启发或实用的参考。
🌱 无论你是刚入门的新手，还是正在进阶的开发者，希望你都能有所收获！

---

🔁 数据结构与算法：有向图的环检测 —— DFS 与拓扑排序的两种方案 🔄

在复杂的系统中，依赖关系无处不在。无论是软件项目中的模块引用 💻，课程学习的先修要求 📚，还是任务调度的执行顺序 ⏳，这些都可以用有向图（Directed Graph） 来建模。

然而，一个关键问题随之而来：是否存在循环依赖？例如：

• 模块 A 依赖 B，B 依赖 C，C 又依赖 A？ ❌
• 课程 C1 要求先修 C2，C2 要求先修 C3，C3 又要求先修 C1？ ❌
• 任务 T1 必须在 T2 之后，T2 在 T3 之后，T3 又在 T1 之后？ ❌

这种“鸡生蛋，蛋生鸡”的循环被称为环（Cycle）。它的存在会导致系统无法正常工作——编译失败、课程无法修完、任务无法执行。

因此，检测有向图中的环是一项至关重要的任务。本文将深入探讨两种经典且高效的解决方案：

1. 深度优先搜索（DFS）标记法 🧭
2. 拓扑排序（Topological Sorting） 📊

我们将结合 Java 代码实现 💻、Mermaid 可视化图表 📈 和 权威参考资料 🔗，全面解析这两种方案的原理与应用。

---

🔄 为什么环检测如此重要？

环的存在会破坏系统的有向无环性（Directed Acyclic Graph, DAG）。DAG 是许多算法和系统的基础假设。

• 编译系统：如果源文件存在循环依赖，编译器无法确定编译顺序。
• 任务调度：如果任务依赖形成环，没有任何任务可以开始执行。
• 数据库事务：循环依赖可能导致死锁。
• 版本控制系统：分支合并时的环可能导致冲突无法解决。

因此，环检测不仅是理论问题，更是工程实践中的安全防线。

---

🧭 方案一：基于 DFS 的环检测

DFS 不仅可以用于遍历，还能通过状态标记来检测环。

🔤 核心思想：三色标记法

我们为每个节点维护三种状态：

• 白色（未访问）：节点尚未被发现。
• 灰色（正在访问）：节点已被发现，但其邻居尚未全部处理完（在递归栈中）。
• 黑色（访问完成）：节点及其所有后代都已被处理完毕。

环的判定条件：在 DFS 过程中，如果从当前节点 u 发现一个灰色的邻居 v，则说明存在一条从 v 到 u 的路径，再加上边 (u,v)，就形成了一个环。

🎨 可视化 DFS 环检测

graph TD
    subgraph 状态说明
        W((白色)):::white
        G((灰色)):::gray
        B((黑色)):::black
    end

    subgraph 图结构
        A((A))
        B((B))
        C((C))
        D((D))
        
        A --> B
        B --> C
        C --> D
        D --> B  <!-- 环：B->C->D->B -->
    end

    style A fill:#fff,stroke:#333
    style B fill:#fff,stroke:#333
    style C fill:#fff,stroke:#333
    style D fill:#fff,stroke:#333

    classDef white fill:#fff,stroke:#333
    classDef gray fill:#f96,stroke:#333,color:#fff
    classDef black fill:#69f,stroke:#333,color:#fff

    click A "https://en.wikipedia.org/wiki/Cycle_detection" "Cycle Detection - Wikipedia"

遍历过程：

1. A (白 → 灰)：访问 A。
2. B (白 → 灰)：A 的邻居 B。
3. C (白 → 灰)：B 的邻居 C。
4. D (白 → 灰)：C 的邻居 D。
5. B (灰)：D 的邻居 B 已是灰色！✅ 发现环。

---

💻 Java 实现：DFS 环检测

import java.util.*;

public class DirectedGraphCycleDFS {
    private List<List<Integer>> adjList;
    private int numVertices;

    public DirectedGraphCycleDFS(int numVertices) {
        this.numVertices = numVertices;
        this.adjList = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v); // 有向边 u -> v
    }

    // 检测图中是否存在环
    public boolean hasCycle() {
        // 0: 白色 (未访问), 1: 灰色 (正在访问), 2: 黑色 (访问完成)
        int[] color = new int[numVertices];
        
        for (int i = 0; i < numVertices; i++) {
            if (color[i] == 0) { // 从每个未访问的节点开始 DFS
                if (dfs(i, color)) {
                    return true; // 发现环
                }
            }
        }
        return false; // 无环
    }

    private boolean dfs(int node, int[] color) {
        color[node] = 1; // 标记为灰色（正在访问）

        for (int neighbor : adjList.get(node)) {
            if (color[neighbor] == 0) {
                // 邻居未访问，递归检查
                if (dfs(neighbor, color)) {
                    return true;
                }
            } else if (color[neighbor] == 1) {
                // 邻居是灰色，发现环
                return true;
            }
            // color[neighbor] == 2: 黑色，已处理完毕，无环
        }

        color[node] = 2; // 回溯，标记为黑色（访问完成）
        return false;
    }

    // 测试
    public static void main(String[] args) {
        DirectedGraphCycleDFS graph = new DirectedGraphCycleDFS(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1); // 形成环 1->2->3->1

        System.out.println("图中存在环: " + graph.hasCycle()); // 输出: true
    }
}

🔍 代码解析

• color[] 数组：实现三色标记，0=白, 1=灰, 2=黑。
• dfs 方法：
  • 入口：将当前节点标记为灰色。
  • 遍历邻居：若邻居为白色，递归；若为灰色，返回 true（有环）。
  • 出口：将当前节点标记为黑色。
• hasCycle 方法：对每个未访问节点启动 DFS，确保处理所有连通分量。

---

📊 方案二：基于拓扑排序的环检测

拓扑排序（Topological Sorting） 是对有向无环图（DAG）的顶点进行线性排序，使得对于每条有向边 (u,v)，u 在排序中都出现在 v 之前。

关键洞察：一个有向图存在拓扑排序 当且仅当 它是无环的。

因此，我们可以通过尝试进行拓扑排序来检测环。如果排序成功，无环；如果失败（无法找到入度为 0 的节点），则存在环。

🧩 Kahn 算法（基于入度）

1. 计算每个节点的入度（in-degree）（指向它的边数）。
2. 将所有入度为 0 的节点加入队列。
3. 从队列中取出节点 u，将其加入拓扑序列。
4. 遍历 u 的所有邻居 v，将 v 的入度减 1。如果 v 的入度变为 0，加入队列。
5. 重复步骤 3-4，直到队列为空。
6. 如果拓扑序列的长度等于节点总数，则无环；否则，存在环。

---

💻 Java 实现：拓扑排序环检测

import java.util.*;

public class DirectedGraphCycleKahn {
    private List<List<Integer>> adjList;
    private int numVertices;

    public DirectedGraphCycleKahn(int numVertices) {
        this.numVertices = numVertices;
        this.adjList = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
    }

    // 检测环：通过拓扑排序
    public boolean hasCycle() {
        int[] inDegree = new int[numVertices];
        
        // 计算每个节点的入度
        for (int u = 0; u < numVertices; u++) {
            for (int v : adjList.get(u)) {
                inDegree[v]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为 0 的节点入队
        for (int i = 0; i < numVertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int visitedCount = 0; // 记录已访问（排序）的节点数

        while (!queue.isEmpty()) {
            int u = queue.poll();
            visitedCount++; // 处理节点 u

            // 遍历 u 的所有邻居
            for (int v : adjList.get(u)) {
                inDegree[v]--; // 移除边 u->v
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 如果所有节点都被访问，则无环
        return visitedCount != numVertices;
    }

    // 获取拓扑排序（如果无环）
    public List<Integer> topologicalSort() {
        // ... (同上计算 inDegree 和队列)
        int[] inDegree = new int[numVertices];
        for (int u = 0; u < numVertices; u++) {
            for (int v : adjList.get(u)) {
                inDegree[v]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numVertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();

        while (!queue.isEmpty()) {
            int u = queue.poll();
            topoOrder.add(u);

            for (int v : adjList.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        if (topoOrder.size() == numVertices) {
            return topoOrder;
        } else {
            return new ArrayList<>(); // 存在环，返回空
        }
    }

    // 测试
    public static void main(String[] args) {
        DirectedGraphCycleKahn graph = new DirectedGraphCycleKahn(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1); // 环

        System.out.println("图中存在环: " + graph.hasCycle()); // true
        System.out.println("拓扑排序: " + graph.topologicalSort()); // []
    }
}

🔍 代码解析

• inDegree[] 数组：存储每个节点的入度。
• queue：存储当前入度为 0 的节点。
• visitedCount：统计成功排序的节点数。
• 环的判定：visitedCount != numVertices 表示有节点无法入队（入度始终 >0），即存在环。

---

🎨 可视化拓扑排序过程

过程：

1. 初始：A 入度为 0，入队。
2. 处理 A：移除 A，B 入度变为 0，入队。
3. 处理 B：C 入度变为 0，入队。
4. 处理 C：D 入度变为 0，入队。
5. 处理 D：B 入度减 1，但 B 已被处理？矛盾！实际上，由于环的存在，D 处理后 B 入度仍为 1（来自 D->B），但 B 已出队，无法再处理。最终 visitedCount=4，但图有 4 个节点，看似无环？⚠️

注意：在有环图中，Kahn 算法会提前终止，visitedCount 小于 numVertices。上述图示简化了过程，实际代码中会正确检测到环。

---

⚖️ DFS vs 拓扑排序：如何选择？

特性	DFS 方案	拓扑排序（Kahn）方案
时间复杂度	O(V + E)	O(V + E)
空间复杂度	O(V)（递归栈）	O(V)（队列 + 入度数组）
是否需要额外数据结构	否（仅需 color 数组）	是（入度数组 + 队列）
能否得到拓扑序	否（除非修改）	✅ 是
实现难度	中等（需理解递归栈）	简单（直观）
适用场景	纯环检测	环检测 + 拓扑排序需求

选择建议：

• 只检测环：两种方案均可，DFS 稍简洁。
• 需要拓扑排序：直接使用 Kahn 算法。
• 避免递归栈溢出：Kahn 算法使用迭代，更安全。

---

🔗 权威参考资料（可访问）

• 📘 维基百科 - 环检测
  全面介绍环检测的各种算法。

• 📚 GeeksforGeeks - 拓扑排序
  包含 DFS 和 Kahn 两种实现。

• 🎓 Khan Academy - 拓扑排序
  免费课程，适合初学者。

• 🧪 Visualgo - 拓扑排序
  交互式动画，直观理解算法过程。

---

🚀 总结

检测有向图中的环是确保系统稳定性的关键步骤。本文介绍了两种经典方案：

1. DFS 三色标记法：利用递归栈的状态（灰色节点）检测环，代码简洁高效。
2. 拓扑排序（Kahn 算法）：通过入度和队列进行排序，失败即表示有环，同时可获得拓扑序。

两者时间复杂度均为 O(V + E)，在实际应用中可根据需求选择。

掌握环检测，你不仅能避免“循环依赖”的陷阱，还能为任务调度、依赖解析等复杂系统打下坚实基础。继续探索，你会发现图算法世界的更多奥秘！✨

---

🙌 感谢你读到这里！
🔍 技术之路没有捷径，但每一次阅读、思考和实践，都在悄悄拉近你与目标的距离。
💡 如果本文对你有帮助，不妨 👍 点赞、📌 收藏、📤 分享 给更多需要的朋友！
💬 欢迎在评论区留下你的想法、疑问或建议，我会一一回复，我们一起交流、共同成长 🌿
🔔 关注我，不错过下一篇干货！我们下期再见！✨