> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/10.-graph/introduction/you-xiang-tu-de-huan-jian-ce.md).

# 有向图的环检测

***Version 1: BFS+Adjacency List** （Leetcode的207）*

BFS的解法，用邻接表表示图（这里的邻接表用List\<List<>>表示，而不是List\<HashSet<>>,因为Testcase中二维数组有重复的所以用List而不用Set，对于重复的边，它在邻接表中村了两份，同时计算入度时也算了两次）一位数组indegree来表示每个顶点的[入度](http://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree)。

我们开始先根据输入来建立这个有向图，同时将入度数组indegree也初始化好。

然后我们定义一个queue变量，将所有入度为0的点放入队列中，

然后开始遍历队列，从graph里遍历其连接的点，每到达一个新节点，将其入度减一，如果此时该点入度为0，则放入队列末尾。

直到遍历完队列中所有的值，若此时还有节点的入度不为0，则说明环存在，返回false，反之则返回true.

\---------------------------------------------------------------------

其实 BFS 算法借助 `indegree` 数组记录每个节点的「入度」，也可以实现这两个算法。不熟悉 BFS 算法的读者可阅读前文 [BFS 算法核心框架](https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==\&mid=2247485134\&idx=1\&sn=fd345f8a93dc4444bcc65c57bb46fc35\&scene=21#wechat_redirect)。

所谓「出度」和「入度」是「有向图」中的概念，很直观：如果一个节点`x`有`a`条边指向别的节点，同时被`b`条边所指，则称节点`x`的出度为`a`，入度为`b`。

先说环检测算法，直接看 BFS 的解法代码：

```
// 主函数
public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 建图，有向边代表「被依赖」关系
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    // 构建入度数组
    int[] indgree = new int[numCourses];
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 节点 to 的入度加一
        indgree[to]++;
    }

    // 根据入度初始化队列中的节点
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indgree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.offer(i);
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.isEmpty()) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        int cur = q.poll();
        count++;
        for (int next : graph[cur]) {
            indgree[next]--;
            if (indgree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.offer(next);
            }
        }
    }

    // 如果所有节点都被遍历过，说明不成环
    return count == numCourses;
}


// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
    // 见前文
}
```

我先总结下这段 BFS 算法的思路：

1、构建邻接表，和之前一样，边的方向表示「被依赖」关系。

2、构建一个 `indegree` 数组记录每个节点的入度，即 `indegree[i]` 记录节点 `i` 的入度。

3、对 BFS 队列进行初始化，将入度为 0 的节点首先装入队列。

**4、开始执行 BFS 循环，不断弹出队列中的节点，减少相邻节点的入度，并将入度变为 0 的节点加入队列**。

**5、如果最终所有节点都被遍历过（`count` 等于节点数），则说明不存在环，反之则说明存在环**。

我画个图你就容易理解了，比如下面这幅图，节点中的数字代表该节点的入度：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8jHKbKcyE7aWJjwf0IBYa92jYws3HpXIK1Fkeqy2l7JW7RzKZ1ic58kg/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

队列进行初始化后，入度为 0 的节点首先被加入队列：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A87owicnBbswicCTa4EziaicLibosTCKyrUhPXd8rhUqic7COY2o8RUmnvpTbQ/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

开始执行 BFS 循环，从队列中弹出一个节点，减少相邻节点的入度，同时将新产生的入度为 0 的节点加入队列：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8Y0U4KgzPibBLp0dHO70gIZVwSqcbJDO7JAovGFQ4jyadAOnLib9r6kfA/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

继续从队列弹出节点，并减少相邻节点的入度，这一次没有新产生的入度为 0 的节点：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8fSrmVoQgibN3xBOxykRvv3034XeoYTjkBVN91SCSJAcicS6NOONbhX3Q/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

继续从队列弹出节点，并减少相邻节点的入度，同时将新产生的入度为 0 的节点加入队列：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8MvERL2HgbAE5H7WXBhnBwZCZZhRfTUsDRxibD3VU48O0ryNfuCVU8oQ/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

继续弹出节点，直到队列为空：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8we63TZF8vgFHnJN9a0kmN9NichW1oIlxzeiaPVRdFAaq65227plTLsOA/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

这时候，所有节点都被遍历过一遍，也就说明图中不存在环。

反过来说，如果按照上述逻辑执行 BFS 算法，存在节点没有被遍历，则说明成环。

比如下面这种情况，队列中最初只有一个入度为 0 的节点：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8WrVYMFx0HH8XjD4ic41cibJHNahVMcmrKS7iaO1mVlFU2KlFHe13tExNA/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

当弹出这个节点并减小相邻节点的入度之后队列为空，但并没有产生新的入度为 0 的节点加入队列，所以 BFS 算法终止：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8sY5mq6y7q68yu6tP0Sgr8DskfCBrQricAzeciaRFqPqVs4iboN354M8MA/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)

你看到了，如果存在节点没有被遍历，那么说明图中存在环，现在回头去看 BFS 的代码，你应该就很容易理解其中的逻辑了。

***Version 2: DFS+Adjacency List** （Leetcode的207）*

用visited 和onPath数组来做图的DFS。

```
// 记录一次递归堆栈中的节点
boolean[] onPath;
// 记录遍历过的节点，防止走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;

boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);

    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];

    for (int i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i);
    }
    // 只要没有循环依赖可以完成所有课程
    return !hasCycle;
}

void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 出现环
        hasCycle = true;
    }

    if (visited[s] || hasCycle) {
        // 如果已经找到了环，也不用再遍历了
        return;
    }
    // 前序代码位置
    visited[s] = true;
    onPath[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序代码位置
    onPath[s] = false;
}

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 代码见前文
}
```

不过如果出题人继续恶心你，让你不仅要判断是否存在环，还要返回这个环具体有哪些节点，怎么办？

你可能说，`onPath` 里面为 true 的索引，不就是组成环的节点编号吗？

不是的，假设下图中绿色的节点是递归的路径，它们在 `onPath` 中的值都是 true，但显然成环的节点只是其中的一部分：

![Image](https://mmbiz.qpic.cn/sz_mmbiz_jpg/gibkIz0MVqdHwMibcEnDibx7E26FaAQl1A8pHNYGPe6tvAfJu8MQdAjmYkFARpDEKj52TNicrtuFKHEJ6LEjwkniceg/640?wx_fmt=jpeg\&wxfrom=5\&wx_lazy=1\&wx_co=1)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/10.-graph/introduction/you-xiang-tu-de-huan-jian-ce.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.