理解无向图中的环
在图论中，环（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 操作的优化，在查找代表元的过程中，将路径上的所有节点的父节点直接指向代表元，从而扁平化树结构。
算法步骤
- 创建一个 DisjointSet 数据结构，初始化时将图中的每个节点都视为一个独立的集合。
- 遍历图中的所有边（每条边只处理一次，例如只处理 (u, v) 而不处理 (v, u)）。
- 对于每条边 (u, v)：
- 调用 ds.find(u) 找到 u 的代表元 rootU。
- 调用 ds.find(v) 找到 v 的代表元 `rootV
