如何检测无向图中的环路

import java.util.*;  public class UndirectedGraphCycleDetector {      private Map<String, List<String>> adj; // 邻接表表示图     private Set<String> visited;         // 记录已访问的节点     private Map<String, String> parent;  // 记录节点的父节点      public UndirectedGraphCycleDetector(Map<String, List<String>> graph) {         this.adj = graph;         this.visited = new HashSet<>();         this.parent = new HashMap<>();     }      /**      * 检测图中是否存在环路      * @return 如果存在环路则返回 true，否则返回 false      */     public boolean hasCycle() {         // 遍历所有顶点，以防图不是连通的         for (String vertex : adj.keySet()) {             if (!visited.contains(vertex)) {                 if (dfs(vertex, null)) { // 从未访问的顶点开始DFS，初始父节点为null                     return true;                 }             }         }         return false;     }      /**      * 深度优先搜索辅助函数      * @param u 当前访问的顶点      * @param p u的父节点      * @return 如果从u开始的路径中存在环路则返回 true，否则返回 false      */     private boolean dfs(String u, String p) {         visited.add(u); // 标记当前节点已访问         parent.put(u, p); // 记录父节点          // 遍历u的所有邻居         if (adj.containsKey(u)) { // 确保u在图中存在邻居列表             for (String v : adj.get(u)) {                 if (!visited.contains(v)) {                     // 如果邻居v未被访问，则递归访问v                     if (dfs(v, u)) {                         return true; // 如果子递归发现环，则返回true                     }                 } else if (!v.equals(p)) {                     // 如果邻居v已被访问，且v不是u的父节点，则发现环路                     // (v.equals(p)是为了避免误判通过父节点回溯的情况)                     return true;                 }             }         }         return false; // 从当前节点出发未发现环路     }      public static void main(String[] args) {         // 示例1: 无环图 (a-b, a-e, c-b, c-d)         Map<String, List<String>> graph1 = new HashMap<>();         graph1.put("a", Arrays.asList("b", "e"));         graph1.put("b", Arrays.asList("a", "c"));         graph1.put("c", Arrays.asList("b", "d"));         graph1.put("d", Arrays.asList("c"));         graph1.put("e", Arrays.asList("a"));         UndirectedGraphCycleDetector detector1 = new UndirectedGraphCycleDetector(graph1);         System.out.println("Graph 1 has cycle: " + detector1.hasCycle()); // Expected: false          // 示例2: 有环图 (a-b, b-c, c-a)         Map<String, List<String>> graph2 = new HashMap<>();         graph2.put("a", Arrays.asList("b", "c"));         graph2.put("b", Arrays.asList("a", "c"));         graph2.put("c", Arrays.asList("a", "b"));         UndirectedGraphCycleDetector detector2 = new UndirectedGraphCycleDetector(graph2);         System.out.println("Graph 2 has cycle: " + detector2.hasCycle()); // Expected: true          // 示例3: 包含孤立节点或非连通分量         Map<String, List<String>> graph3 = new HashMap<>();         graph3.put("x", Arrays.asList("y"));         graph3.put("y", Arrays.asList("x"));         graph3.put("z", new ArrayList<>()); // 孤立节点         graph3.put("p", Arrays.asList("q"));         graph3.put("q", Arrays.asList("p"));         UndirectedGraphCycleDetector detector3 = new UndirectedGraphCycleDetector(graph3);         System.out.println("Graph 3 has cycle: " + detector3.hasCycle()); // Expected: false     } }

import java.util.*;  public class UndirectedGraphCycleDetectorUnionFind {      // 存储每个元素的父节点     private Map<String, String> parent;     // 存储每个集合的秩（用于优化union操作，减少树的高度）     private Map<String, Integer> rank;      public UndirectedGraphCycleDetectorUnionFind(Set<String> vertices) {         parent = new HashMap<>();         rank = new HashMap<>();         // 初始化：每个顶点都是自己的父节点，秩为0         for (String vertex : vertices) {             parent.put(vertex, vertex);             rank.put(vertex, 0);         }     }      /**      * 查找元素所在集合的代表（根节点），并进行路径压缩      * @param i 要查找的元素      * @return 元素所在集合的代表      */     private String find(String i) {         if (!parent.get(i).equals(i)) {             // 路径压缩：将i直接连接到其根节点             parent.put(i, find(parent.get(i)));         }         return parent.get(i);     }      /**      * 合并两个元素所在的集合（按秩合并）      * @param i 元素1      * @param j 元素2      * @return 如果成功合并（即i和j原来不在同一个集合中）返回 true，否则返回 false      */     private boolean union(String i, String j) {         String rootI = find(i);         String rootJ = find(j);          if (!rootI.equals(rootJ)) { // 如果不在同一个集合中，则合并             // 按秩合并：将秩较小的树连接到秩较大的树的根上             if (rank.get(rootI) < rank.get(rootJ)) {                 parent.put(rootI, rootJ);             } else if (rank.get(rootJ) < rank.get(rootI)) {                 parent.put(rootJ, rootI);             } else { // 秩相等时，任意一个作为根，并增加其秩                 parent.put(rootJ, rootI);                 rank.put(rootI, rank.get(rootI) + 1);             }             return true;         }         return false; // 已经在同一个集合中，合并失败（意味着发现环）     }      /**      * 检测图中是否存在环路      * @param edges 图的边列表，每条边表示为一对字符串 (u, v)      * @return 如果存在环路则返回 true，否则返回 false      */     public boolean hasCycle(List<String[]> edges) {         for (String[] edge : edges) {             String u = edge[0];             String v = edge[1];              String rootU = find(u);             String rootV = find(v);              if (rootU.equals(rootV)) {                 // 如果u和v的根节点相同，说明它们已经在同一个连通分量中，                 // 添加这条边会形成环路                 return true;             } else {                 // 否则，合并u和v所在的集合                 union(u, v);             }         }         return false;     }      public static void main(String[] args) {         // 示例1: 无环图 (a-b, a-e, c-b, c-d)         Set<String> vertices1 = new HashSet<>(Arrays.asList("a", "b", "c", "d", "e"));         List<String[]> edges1 = Arrays.asList(             new String[]{"a", "b"},             new String[]{"a", "e"},             new String[]{"c", "b"},             new String[]{"c", "d"}         );         UndirectedGraphCycleDetectorUnionFind detector1 = new UndirectedGraphCycleDetectorUnionFind(vertices1);         System.out.println("Graph 1 has cycle: " + detector1.hasCycle(edges1)); // Expected: false          // 示例2: 有环图 (a-b, b-c, c-a)         Set<String> vertices2 = new HashSet<>(Arrays.asList("a", "b", "c"));         List<String[]> edges2 = Arrays.asList(             new String[]{"a", "b"},             new String[]{"b", "c"},             new String[]{"c", "a"}         );         UndirectedGraphCycleDetectorUnionFind detector2 = new UndirectedGraphCycleDetectorUnionFind(vertices2);         System.out.println("Graph 2 has cycle: " + detector2.hasCycle(edges2)); // Expected: true          // 示例3: 包含孤立节点或非连通分量 (并查集主要关注边，只要边不形成环即可)         Set<String> vertices3 = new HashSet<>(Arrays.asList("x", "y", "z", "p", "q"));         List<String[]> edges3 = Arrays.asList(             new String[]{"x", "y"},             new String[]{"p", "q"}         );         UndirectedGraphCycleDetectorUnionFind detector3 = new UndirectedGraphCycleDetectorUnionFind(vertices3);         System.out.println("Graph 3 has cycle: " + detector3.hasCycle(edges3)); // Expected: false     } }