1. 理解无向图中的循环
在图论中，一个循环（Cycle）是指从图中的某个顶点出发，沿着一系列边最终回到该顶点的路径，且路径上的所有顶点（除了起点和终点）都不重复。在无向图中，由于边是双向的，因此简单地沿着一条边再立即返回不算作循环。循环检测在许多图算法中至关重要，例如判断图是否为树、拓扑排序的先决条件（有向无环图DAG）、最小生成树算法等。
2. 方法一：基于深度优先搜索（DFS）的循环检测
深度优先搜索是一种遍历图的算法，它尽可能深地探索图的分支。在无向图中，DFS可以有效地检测循环，其核心思想是识别“回边”（Back-Edge）。
2.1 核心思想：回边检测
在DFS遍历过程中，如果从当前顶点 u 访问其邻接点 v 时，发现 v 已经被访问过，并且 v 不是 u 的直接父节点，那么就意味着存在一条从 u 到 v 的边，而 v 已经在当前DFS路径上，这条边 (u, v) 就构成了一个循环。
2.2 算法原理
-
初始化：
- 使用一个集合或布尔数组 visited 来记录已被访问的顶点。
- 使用一个映射 parent 来记录每个顶点在DFS遍历树中的父节点。
-
遍历：
- 对图中的每个顶点执行DFS。这是为了确保处理非连通图中的所有组件。
- 从一个未访问的顶点 u 开始DFS，并将其标记为已访问。
- 对于 u 的每一个邻接点 v：
- 如果 v 未被访问，则将 u 设为 v 的父节点，并递归地对 v 执行DFS。如果在递归调用中发现循环，则立即返回 true。
- 如果 v 已经被访问，并且 v 不是 u 的父节点（即 v 不是我们从哪里来到 u 的那个顶点），则说明找到了一条回边，存在循环，返回 true。
- 返回： 如果整个DFS过程完成，没有发现任何回边，则说明图中不存在循环，返回 false。
2.3 示例代码（Java-like Pseudocode）
import java.util.*;
class GraphDFS {
private Map<String, List<String>> adj; // 邻接列表表示图
private Set<String> visited; // 记录已访问的节点
private Map<String, String> parent; // 记录节点的父节点
public GraphDFS(Map<String, List<String>> adjacencyList) {
this.adj = adjacencyList;
}
/**
* 检测无向图中是否存在循环。
* @return 如果存在循环返回 true，否则返回 false。
*/
public boolean hasCycle() {
visited = new HashSet<>();
parent = new HashMap<>();
// 遍历所有节点，确保处理非连通图中的所有组件
// 收集所有可能的节点，包括那些没有邻居的节点
Set<String> allNodes = new HashSet<>(adj.keySet());
for (List<String> neighbors : adj.values()) {
allNodes.addAll(neighbors);
}
for (String node : allNodes) {
if (!visited.contains(node)) {
// 从未访问的节点开始DFS，父节点设为null
if (dfs(node, null)) {
return true; // 发现循环
}
}
}
return false; // 没有发现循环
}
/**
* 深度优先搜索辅助函数。
* @param u 当前访问的节点
* @param p u的父节点
* @return 如果在当前DFS路径中发现循环返回 true，否则返回 false。
*/
private boolean dfs(String u, String p) {
visited.add(u); // 标记当前节点为已访问
parent.put(u, p); // 记录父节点
// 遍历当前节点的所有邻接点
for (String v : adj.getOrDefault(u, Collections.emptyList())) {
if (!visited.contains(v)) {
// 如果邻接点v未被访问，则递归地进行DFS
if (dfs(v, u)) {
return true; // 递归调用发现循环
}
} else if (!v.equals(p)) {
// 如果邻接点v已被访问，且v不是u的父节点，则发现回边，存在循环
return true;
}
}
return false; // 当前路径中未发现循环
}
}2.4 注意事项
- 处理非连通图： 外层循环 for (String node : allNodes) 是必要的，以确保即使图包含多个不连通的组件，也能全面检测。
- 父节点检查： !v.equals(p) 是避免将DFS路径中直接相邻的父子边误判为循环的关键。在无向图中，边 (u, v) 意味着 v 是 u 的邻居，同时 u 也是 v 的邻居。如果 v 是 u 的父节点，那么 (u, v) 只是DFS树中的一条正常边，不是循环。
3. 方法二：基于并查集（Union-Find）的循环检测
并查集（Disjoint Set Union, DSU）是一种用于处理不相交集合的数据结构，它能够高效地执行“查找”（Find）和“合并”（Union）操作。在无向图中，并查集特别适用于检测循环。
3.1 核心思想：集合合并与查找
并查集将图中的每个顶点视为一个独立的集合。当我们遍历图中的每条边 (u, v) 时：
- 如果 u 和 v 已经在同一个集合中（即它们的代表元素相同），那么添加这条边 (u, v) 将会形成一个循环。
- 如果 u 和 v 不在同一个集合中，则将它们所在的集合合并。
3.2 算法原理
-
初始化：
- 为图中的每个顶点创建一个独立的集合，即每个顶点的父节点指向自身。
- 可选地，维护一个 rank 或 size 数组/映射来优化合并操作（按秩合并或按大小合并），以及路径压缩来优化查找操作。
-
遍历边：
- 遍历图中的所有边 (u, v)。对于无向图，每条边通常只处理一次（例如，如果边 (a, b) 已处理，则不再处理 (b, a)）。
- 对于每条边 (u, v)：
- 使用 find(u) 查找 u 的代表元素（根节点）。
- 使用 find(v) 查找 v 的代表元素（根节点）。
- 如果 find(u) 等于 find(v)，说明 u 和 v 已经通过其他路径连通，现在再添加边 (u, v) 就会形成一个循环，返回 true。
- 如果 find(u) 不等于 find(v)，说明 u 和 v 属于不同的连通分量，此时执行 union(u, v) 操作，将这两个连通分量合并。
- 返回： 如果所有边都被处理完毕，没有发现任何循环，则返回 false。
3.3 示例代码（Java-like Pseudocode）
import java.util.*;
class UnionFind {
private Map<String, String> parent; // 存储每个元素的父节点
private Map<String, Integer> rank; // 存储每个集合的秩（用于按秩合并优化）
public UnionFind(Set<String> nodes) {
parent = new HashMap<>();
rank = new HashMap<>();
for (String node : nodes) {
parent.put(node, node); // 初始时每个节点的父节点是自己
rank.put(node, 0); // 初始秩为0
}
}
/**
* 查找元素i的代表元素（根节点），并进行路径压缩。
* @param i 要查找的元素
* @return 元素i的代表元素
*/
public String find(String i) {
if (!parent.containsKey(i)) {
// 如果节点不在并查集中，可以根据需求处理，例如抛出异常或返回自身
parent.put(i, i);
rank.put(i, 0);
return i;
}
if (parent.get(i).equals(i)) {
return i;
}
String root = find(parent.get(i)); // 递归查找根
parent.put(i, root); // 路径压缩
return root;
}
/**
* 合并元素i和j所在的集合。
* @param i 元素i
* @param j 元素j
* @return 如果成功合并（未形成循环）返回 true，否则返回 false（已在同一集合，形成循环）。
*/
public 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(rootI) > rank.get(rootJ)) {
parent.put(rootJ, rootI);
} else { // 秩相等时，任意连接，并将新根的秩加1
parent.put(rootJ, rootI);
rank.put(rootI, rank.get(rootI) + 1);
}
return true; // 合并成功，未形成循环
}
return false; // 已经在同一个集合，添加这条边会形成循环
}
}
class GraphUnionFind {
private Map<String, List<String>> adj; // 邻接列表表示图
public GraphUnionFind(Map<String, List<String>> adjacencyList) {
this.adj = adjacencyList;
}
/**
* 检测无向图中是否存在循环。
* @return 如果存在循环返回 true，否则返回 false。
*/
public boolean hasCycle() {
// 收集所有节点，包括那些没有邻居的节点
Set<String> allNodes = new HashSet<>(adj.keySet());
for (List<String> neighbors : adj.values()) {
allNodes.addAll(neighbors);
}
UnionFind uf = new UnionFind(allNodes);
// 遍历所有边。对于无向图，每条边 (u,v) 会在邻接列表中出现两次
// 我们需要确保每条边只被处理一次，以避免重复判断或错误判断
Set<String> processedEdges = new HashSet<>(); // 用于记录已处理的边对，例如 "a-b"
for (String u : adj.keySet()) {
for (String v : adj.getOrDefault(u, Collections.emptyList())) {
// 确保只处理一次边 (u,v)，例如通过规范化边表示或跳过已处理的逆向边
String edge 
