无向图环路检测：DFS与并查集详解

“纵有疾风来，人生不言弃”，这句话送给正在学习文章的朋友们，也希望在阅读本文《无向图环路检测：DFS与并查集全解析》后，能够真的帮助到大家。我也会在后续的文章中，陆续更新文章相关的技术文章，有好的建议欢迎大家在评论留言，非常感谢！

无向图环路检测概述

在图论中，环路（Cycle）是指从一个节点出发，经过一系列边，最终回到该节点的路径。对于无向图而言，环路的存在意味着图中存在冗余的连接。检测无向图中的环路是许多图算法的基础，例如判断图是否为树（无环连通图）、最小生成树算法等。

检测无向图环路主要有两种经典且高效的方法：深度优先搜索（DFS）和并查集（Union-Find）算法。虽然广度优先搜索（BFS）也可以用于环路检测，但其逻辑相比DFS更为复杂，且不如DFS或Union-Find直观。

方法一：深度优先搜索 (DFS) 检测环路

深度优先搜索（DFS）是一种遍历或搜索树或图的算法。它沿着一条路径尽可能深地搜索，直到到达末端，然后回溯。在无向图中，DFS可以巧妙地用于检测环路。

DFS 检测环路的核心思想

DFS检测无向图环路的关键在于跟踪每个节点的访问状态以及其父节点。当DFS遍历到一个邻居节点时，如果该邻居节点已经被访问过，并且它不是当前节点的直接父节点，那么就意味着发现了一个环路。

• 访问状态：我们需要一个机制来记录哪些节点已经被访问过。通常使用一个布尔数组或集合 visited 来标记。
• 父节点跟踪：在递归调用DFS时，需要将当前节点作为参数传递给其子节点的“父节点”参数。这可以防止将当前节点与其直接父节点之间的边误判为环路。

算法步骤

1. 初始化一个 visited 集合（或数组）来跟踪已访问的节点，以及一个 parent 映射来记录每个节点的父节点。
2. 遍历图中的所有节点。对于每个未访问的节点，以它为起点调用DFS函数。这是为了确保检测到所有连通分量中的环路。
3. DFS函数 dfs(currentNode, parentNode)：
   • 将 currentNode 标记为已访问。
   • 遍历 currentNode 的所有邻居 neighbor：
     • 如果 neighbor 是 parentNode，则跳过（这是因为无向图的边是双向的，我们不想将 u-v 边视为 v 的环路）。
     • 如果 neighbor 已经被访问过（即在 visited 集合中），则说明找到了一个环路，返回 true。
     • 如果 neighbor 未被访问，则递归调用 dfs(neighbor, currentNode)。如果递归调用返回 true，则说明在子树中找到了环路，当前函数也返回 true。
4. 如果所有DFS调用都完成，且没有返回 true，则图中不存在环路。

示例代码 (Java)

以下是使用Java实现DFS检测无向图环路的示例框架：

import java.util.*;

class GraphDFS {
    private Map> 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 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 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
    }
}

时间复杂度和空间复杂度

• 时间复杂度：O(V + E)，其中V是节点数，E是边数。DFS需要访问每个节点和每条边一次。
• 空间复杂度：O(V + E)，主要用于存储邻接列表、visited 集合以及递归栈的深度（最坏情况下为V）。

方法二：并查集 (Union-Find) 检测环路

并查集（Disjoint Set Union, DSU），也称为不相交集数据结构，是一种用于管理元素所属集合的数据结构。它支持两种主要操作：find（查找元素所属集合的代表）和 union（合并两个集合）。在无向图中，并查集非常适合用于检测环路。

Union-Find 检测环路的核心思想

Union-Find算法通过遍历图中的每条边来检测环路。对于图中的每条边 (u, v)：

1. 查找 u 所属的集合代表（根节点），记为 rootU。
2. 查找 v 所属的集合代表（根节点），记为 rootV。
3. 如果 rootU 和 rootV 相同，这意味着 u 和 v 已经在同一个连通分量中。此时，如果再添加边 (u, v)，就会形成一个环路。
4. 如果 rootU 和 rootV 不同，则将 u 和 v 所在的两个集合合并，表示它们现在连通了。

Union-Find 数据结构简介

Union-Find数据结构通常包含以下组件和优化：

• parent 数组/映射：存储每个元素的父节点。如果 parent[i] == i，则 i 是其所在集合的代表（根节点）。
• find(i) 操作：查找元素 i 的根节点。通常会结合路径压缩优化，将查找路径上的所有节点直接指向根节点，从而加速后续查找。
• union(i, j) 操作：合并包含 i 和 j 的两个集合。通常会结合按秩（或按大小）合并优化，将较小的树连接到较大的树的根节点上，以保持树的平衡，降低树的高度。

算法步骤

1. 初始化并查集数据结构，将图中的每个节点视为一个独立的集合（每个节点的父节点指向自身）。
2. 获取图中的所有边。为了避免重复处理无向图中的边 (u, v) 和 (v, u) 导致误判，通常将所有边存储在一个列表中，或确保每条边只被处理一次。
3. 遍历图中的每一条边 (

到这里，我们也就讲完了《无向图环路检测：DFS与并查集详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！