无向图中的环路检测：深度解析DFS与并查集算法-java教程-PHP中文网

无向图中的环路检测：深度解析DFS与并查集算法

霞舞

发布： 2025-07-21 13:58:32

原创

390人浏览过

无向图中的环路检测：深度解析dfs与并查集算法

本文深入探讨了在无向图中检测环路的两种经典且高效的算法：深度优先搜索（DFS）和并查集（Union-Find）。通过详细阐述它们的核心思想、算法步骤及提供清晰的Java示例代码，文章旨在帮助读者理解如何在无向图中准确地识别环路，并分析了常见实现中的误区，为图算法的学习和实践提供了专业的指导。

理解无向图中的环

在图论中，环（Cycle）是指从图中的一个顶点出发，沿着边经过一系列不同的顶点，最终回到起始顶点的路径。在无向图中，由于边是双向的，因此需要特别注意“父子”关系，以避免将简单的回溯（即从子节点回到父节点）误判为环。检测无向图中的环是许多图算法的基础，例如判断图是否为树（无环连通图）。

方法一：基于深度优先搜索（DFS）的环路检测

深度优先搜索（DFS）是一种遍历图的算法，它从起始顶点开始，尽可能深地探索图的分支，直到达到死胡同或已访问的顶点，然后回溯。在无向图中，DFS检测环的核心思想是：如果在遍历过程中，我们遇到一个已经被访问过的顶点，并且这个顶点不是当前顶点的直接父节点，那么就存在一个环。

百度文心百中

百度大模型语义搜索体验中心

查看详情

核心思想

记录访问状态： 使用一个集合（或布尔数组）来记录每个顶点是否已被访问。
记录父节点： 在DFS递归调用中，传入当前节点的父节点。
判断环： 当DFS访问一个邻居顶点时：
- 如果该邻居顶点未被访问，则继续对其进行DFS遍历，并将当前顶点设为它的父节点。
- 如果该邻居顶点已被访问，并且它不是当前顶点的父节点，则说明找到了一条“回边”（Back Edge），即存在一个环。

算法步骤

初始化一个 visited 集合，用于记录已访问的节点。
初始化一个 parent 映射，用于记录DFS树中每个节点的父节点。
遍历图中的所有节点（以处理非连通图），对于每个未访问的节点，启动一次DFS。
在DFS函数 dfs(currentNode, parentNode, visited, parentMap) 中：
- 将 currentNode 标记为已访问，并记录其父节点 parentNode。
- 遍历 currentNode 的所有邻居 neighbor：
  - 如果 neighbor 是 parentNode，则跳过（这是无向图中的正常回溯边）。
  - 如果 neighbor 已经存在于 visited 集合中，则说明找到了一个环，返回 true。
  - 如果 neighbor 未被访问，则递归调用 dfs(neighbor, currentNode, visited, parentMap)。如果递归调用返回 true，则直接返回 true。
如果所有DFS遍历完成都没有找到环，则返回 false。

示例代码 (Java)

import java.util.*;

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

    public DSGraphDFS() {
        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<>(); // 记录已访问的节点
        // 无需显式parent map，因为DFS函数参数中会传递父节点

        // 遍历所有节点，以处理非连通图
        for (String node : adj.keySet()) {
            if (!visited.contains(node)) {
                // 对于每个未访问的连通分量，启动DFS
                if (dfs(node, null, visited)) { // 初始调用时，父节点为null
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * DFS递归函数，用于检测环路
     * @param u 当前访问的节点
     * @param p u的父节点（在DFS遍历路径中）
     * @param visited 已访问节点集合
     * @return 如果在当前DFS路径中检测到环路，返回true；否则返回false。
     */
    private boolean dfs(String u, String p, Set<String> visited) {
        visited.add(u); // 标记当前节点为已访问

        // 遍历当前节点的所有邻居
        for (String v : adj.getOrDefault(u, Collections.emptyList())) {
            if (v.equals(p)) { // 如果邻居是父节点，跳过，因为这是无向图的正常回溯
                continue;
            }
            if (visited.contains(v)) { // 如果邻居已被访问，且不是父节点，则存在环
                return true; // 发现回边
            }
            // 如果邻居未被访问，则递归进行DFS
            if (dfs(v, u, visited)) {
                return true; // 递归调用中发现了环
            }
        }
        return false; // 当前路径没有发现环
    }

    // 辅助方法，用于获取所有节点，以便初始化DSGraphUnionFind
    public Set<String> getAllNodes() {
        return adj.keySet();
    }
}

登录后复制

注意事项

处理非连通图： hasCycleDFS 方法外部的循环 for (String node : adj.keySet()) 是必要的，它确保即使图是非连通的，也能检测到所有连通分量中的环。
父节点的重要性： 在无向图中，每条边 (u, v) 都可以双向遍历。为了避免将 v 返回到 u 误判为环，需要显式地传递并检查父节点。

方法二：基于并查集（Union-Find）的环路检测

并查集（Disjoint Set Union, DSU）是一种数据结构，用于管理一组不相交的集合。它支持两种主要操作：find（查找元素所属集合的代表元）和 union（合并两个集合）。在无向图中，并查集可以高效地检测环：当处理一条边 (u, v) 时，如果 u 和 v 已经属于同一个集合（即它们已经连通），那么添加这条边就会形成一个环。

核心思想

初始化： 将图中的每个顶点视为一个独立的集合。
处理边： 遍历图中的所有边。对于每条边 (u, v)：
- 使用 find 操作找到 u 和 v 所属集合的代表元。
- 如果 u 和 v 的代表元相同，说明它们已经连通，添加这条边将形成一个环。
- 如果 u 和 v 的代表元不同，说明它们不连通，使用 union 操作将它们所在的集合合并。

并查集基础

parent 数组/映射： 存储每个元素的父节点。如果 parent[i] == i，则 i 是其集合的代表元。
rank 或 size 数组/映射： 用于优化 union 操作，通过将较小的树连接到较大的树（按秩合并或按大小合并），保持树的平衡，从而降低树的高度，优化 find 操作的效率。
路径压缩： find 操作的优化，在查找代表元的过程中，将路径上的所有节点的父节点直接指向代表元，从而扁平化树结构。