0、什么是环？

在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。

在有向图中，一个结点经过两种路线到达另一个结点，未必形成环。

1、拓扑排序

1.1、无向图

使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：

1. 求出图中所有结点的度。
2. 将所有度 <= 1 的结点入队。（独立结点的度为 0）
3. 当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。
4. 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。

1.2、有向图

使用拓扑排序判断无向图和有向图中是否存在环的区别在于：

• 在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；
• 在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。

import java.util.LinkedList;
import java.util.Queue;

public class Graph {
    private int numVertices; // 图的顶点数
    private LinkedList<Integer>[] adj; // 邻接表

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adj = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加边
    public void addEdge(int source, int dest) {
        adj[source].add(dest);
    }

    // 使用拓扑排序检测环
    public boolean isCyclic() {
        int[] inDegree = new int[numVertices];
        for (int i = 0; i < numVertices; i++) {
            for (int node : adj[i]) {
                inDegree[node]++;
            }
        }

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

        int count = 0;
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int node : adj[current]) {
                if (--inDegree[node] == 0) {
                    queue.add(node);
                }
            }
            count++;
        }

        return count != numVertices;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        System.out.println("The graph has a cycle: " + graph.isCyclic());
    }
}

2、DFS

使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。

我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有结点都是白色，当访问过某个结点后，该结点变为灰色，当该结点的所有邻接点都访问完，该节点变为黑色。