Detect Cycle in Undirected Graph Using DSU in Java

2025年3月29日 | 阅读 5 分钟

图中检测环是一个基本问题，在实践中被广泛使用，并且是许多领域的重要工具，如网络设计、社交网络分析以及系统中的环搜索。无向图中的环是指能够通过邻居节点并再次回到该节点的情况。

在本节中，我们将讨论如何使用并查集（也称为Disjoint Set Union）在无向图中检测环。并查集数据结构在动态连通性问题（如无向图中的环检测）中有许多应用。

问题概述

问题在于确定无向图中是否存在环。图可以被建模为节点之间的边集，问题在于发现是否存在连接某个顶点与其祖先顶点的回边，这将暗示一个环。

使用并查集（DSU）的方法

DSU算法通过使用两个主要操作来维护图的连通分量：

Find： 定义节点所属的集合，并找出集合中的根节点或最高权限节点。
Union： 合并两个集合或至少一个集合的两个组件，形成一个集合。

使用DSU，我们可以通过以下方式检测环：

遍历图中的所有边。
对于每条边，执行Find操作以确定边的两个顶点是否属于同一个集合。
如果其中一个顶点属于同一个组，则存在环。
如果它们属于两个不同的集合，则进行Union操作，将两个集合合并。

DSU算法步骤

初始化DSU结构： 在合并之前，初始化一个父数组，其中每个节点最初都指向自身，并使用秩数组以实现高效的Find操作。

Find操作： 必须采用路径压缩技术，通过将节点链接到其根节点来提高查找根节点的过程效率。

Union操作： 为了获得高度最小的短树，建议通过秩合并将子树与大树的根合并。

文件名：CycleDetectionDSU.java

import java.util.*;
public class CycleDetectionDSU {
    // DSU class to perform union-find operations
    static class DSU {
        private int[] parent;
        private int[] rank;
        // Initialize parent and rank arrays
        public DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i; // each node is its own parent initially
                rank[i] = 1;   // rank initialized to 1
            }
        }
        // Find with path compression
        public int find(int node) {
            if (parent[node] != node) {
                parent[node] = find(parent[node]); // path compression
            }
            return parent[node];
        }
        // Union by rank
        public boolean union(int node1, int node2) {
            int root1 = find(node1);
            int root2 = find(node2);
            // If they have the same root, a cycle is detected
            if (root1 == root2) {
                return false;
            }
            // Union by rank
            if (rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else if (rank[root1] < rank[root2]) {
                parent[root1] = root2;
            } else {
                parent[root2] = root1;
                rank[root1]++;
            }
            return true;
        }
    }
    // Method to check if a cycle exists in the undirected graph
    public boolean hasCycle(int[][] edges, int n) {
        DSU dsu = new DSU(n);
        // Iterate through all edges
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            // If the two vertices are already connected, a cycle exists
            if (!dsu.union(u, v)) {
                return true;
            }
        }
        // No cycle detected
        return false;
    }
    public static void main(String[] args) {
        CycleDetectionDSU graph = new CycleDetectionDSU();
        // Example 1: Graph with a cycle
        int[][] edges1 = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
        int n1 = 3; // 3 nodes
        System.out.println("Graph 1 has cycle: " + graph.hasCycle(edges1, n1));
        // Example 2: Graph without a cycle
        int[][] edges2 = { { 0, 1 }, { 1, 2 } };
        int n2 = 3; // 3 nodes
        System.out.println("Graph 2 has cycle: " + graph.hasCycle(edges2, n2));
    }
}   

输出

 
Graph 1 has cycle: true
Graph 2 has cycle: false

解释

DSU类

find() 方法： 这个方法查找节点的根，并应用路径压缩，以确保每个节点到其根都有一个独立的链接，这将降低未来操作的时间复杂度。
Union： 该方法用于根据秩执行集合合并。在这种情况下，如果两个节点属于同一个集合，则表示存在环，并且该方法返回false。否则，合并两个集合，该方法将返回true。

HasCycle() 方法

它接受边和节点数作为参数。它遍历所有边，并对每对节点使用Union方法。如果Union返回false，则表示找到了一个循环，并且该方法退出。

注意事项和边缘情况

不连通图： 对于不连通图，应分别考虑所有连通分量。此实现对于连通分量并查找这些分量内的环效果很好。

自环： 如果一个节点有一条边指向自身，则会立即识别出这是一个环。

多重边： 如果两个节点之间有多条边，第一条边表示两个节点已连接，而其他边则表示环。

结论

我们已详细解释了如何使用并查集（DSU）数据结构来识别无向图中的环。DSU方法的算法适合于DSU问题的有效实现，在图的环检测方面尤其有效。

然而，通过在当前算法中使用路径压缩和按秩合并等有效数据结构，操作复杂度得到优化，为图中的环检测提供了一个可靠的方案。

下一个主题Java中的原始数据类型

Detect Cycle in Undirected Graph Using DSU in Java

问题概述

使用并查集（DSU）的方法

DSU算法步骤

解释

注意事项和边缘情况

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Detect Cycle in Undirected Graph Using DSU in Java

问题概述

使用并查集（DSU）的方法

DSU算法步骤

解释

注意事项和边缘情况

结论

相关帖子

Java 中抽象的实现

DecimalStyle withDecimalSeparator() Method in Java with Examples

Java 中的数组分区问题

实现 Java Queue 接口

Java 中的错误类型

Java 中的无效操作数类型错误

Java 中的嵌套三元运算符

Java 中处理 "Handler dispatch failed" 嵌套异常：java.lang.StackOverflowError

Java 中 OOP 和 POP 的区别

Java 中的 Ganesha 图案

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器