如何在无向图中检测环路？深度优先搜索与并查集算法详解

import java.util.*;

class GraphDFS {
    private Map<String, List<String>> adj; // 邻接列表表示图

    public GraphDFS() {
        adj = new HashMap<>();
    }

    // 添加无向边
    public void addEdge(String u, String v) {
        adj.computeIfAbsent(u, k -> new LinkedList<>()).add(v);
        adj.computeIfAbsent(v, k -> new LinkedList<>()).add(u);
    }

    /**
     * 使用DFS检测无向图中的环路
     * @return 如果图中存在环路，则返回true；否则返回false。
     */
    public boolean hasCycleDFS() {
        Set<String> visited = new HashSet<>(); // 记录已访问的节点

        // 遍历所有节点，确保处理所有连通分量
        for (String node : adj.keySet()) {
            if (!visited.contains(node)) {
                // 对于每个未访问的节点，启动一次DFS遍历
                // null作为初始父节点，表示当前节点没有父节点
                if (dfs(node, null, visited)) {
                    return true; // 发现环路
                }
            }
        }
        return false; // 所有连通分量都检查完毕，没有发现环路
    }

    /**
     * DFS递归函数
     * @param u 当前访问的节点
     * @param parent 父节点，用于避免将回溯边误判为环路
     * @param visited 已访问节点集合
     * @return 如果从当前节点开始的DFS路径中发现环路，则返回true
     */
    private boolean dfs(String u, String parent, Set<String> visited) {
        visited.add(u); // 标记当前节点为已访问

        // 遍历当前节点u的所有邻居
        for (String v : adj.getOrDefault(u, Collections.emptyList())) {
            // 如果邻居v是u的父节点，则跳过，避免将双向边误判为环
            if (v.equals(parent)) {
                continue;
            }
            // 如果邻居v已被访问，且v不是u的父节点，则说明存在一个环路
            if (visited.contains(v)) {
                return true;
            }
            // 如果邻居v未被访问，则递归地对v进行DFS
            if (dfs(v, u, visited)) {
                return true; // 如果子递归发现了环路，则直接返回true
            }
        }
        return false; // 从当前节点出发未发现环路
    }

    public static void main(String[] args) {
        GraphDFS g1 = new GraphDFS();
        g1.addEdge("a", "b");
        g1.addEdge("a", "e");
        g1.addEdge("c", "b");
        g1.addEdge("c", "d");
        System.out.println("Graph 1 (Square graph) has cycle: " + g1.hasCycleDFS()); // 预期: false

        GraphDFS g2 = new GraphDFS();
        g2.addEdge("a", "b");
        g2.addEdge("b", "c");
        g2.addEdge("c", "a"); // 形成环 a-b-c-a
        System.out.println("Graph 2 (Triangle graph) has cycle: " + g2.hasCycleDFS()); // 预期: true

        GraphDFS g3 = new GraphDFS();
        g3.addEdge("a", "b");
        g3.addEdge("b", "c");
        g3.addEdge("c", "d");
        g3.addEdge("d", "a"); // 形成环 a-b-c-d-a
        System.out.println("Graph 3 (Square with diagonal) has cycle: " + g3.hasCycleDFS()); // 预期: true
    }
}