当前位置：首页 > Java

java如何判断闭环

2026-03-24 12:37:55Java

判断闭环的方法

在Java中判断闭环通常涉及图论中的环检测算法，常见场景包括链表、有向图或无向图中的环。以下是几种典型实现方式：

链表中的闭环检测（Floyd判圈算法）

使用快慢指针检测单向链表是否存在环：

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head;
    ListNode fast = head.next;

    while (fast != null && fast.next != null) {
        if (slow == fast) return true;
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

原理：快指针每次移动两步，慢指针移动一步。若存在环，两者必然相遇。

有向图的环检测（DFS着色法）

通过深度优先搜索标记节点状态检测环：

enum Color { WHITE, GRAY, BLACK }; // 未访问、访问中、已访问

public boolean hasCycle(List<List<Integer>> graph) {
    Color[] colors = new Color[graph.size()];
    Arrays.fill(colors, Color.WHITE);

    for (int i = 0; i < graph.size(); i++) {
        if (colors[i] == Color.WHITE && dfs(graph, i, colors)) {
            return true;
        }
    }
    return false;
}

private boolean dfs(List<List<Integer>> graph, int node, Color[] colors) {
    colors[node] = Color.GRAY;
    for (int neighbor : graph.get(node)) {
        if (colors[neighbor] == Color.GRAY) return true;
        if (colors[neighbor] == Color.WHITE && dfs(graph, neighbor, colors)) {
            return true;
        }
    }
    colors[node] = Color.BLACK;
    return false;
}

关键点：遇到GRAY状态节点表示存在后向边，即环。

无向图的环检测（并查集）

使用并查集数据结构检测无向图的环：

class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // 已连通，存在环
        parent[rootY] = rootX;
        return true;
    }
}

public boolean hasCycle(int[][] edges, int n) {
    UnionFind uf = new UnionFind(n);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) return true;
    }
    return false;
}

适用场景：处理无向图的边时，若两个顶点已在同一集合，则存在环。

java如何判断闭环