在无向图中，环路是指从一个顶点出发，沿着一系列边最终能够回到该顶点的路径，且路径上的所有边和顶点（除了起点和终点）都不重复。检测无向图中的环路是图论中的一个基本问题，在网络拓扑、数据结构验证等多个领域都有广泛应用。
深度优先搜索（DFS）是一种遍历图的算法，它从起始顶点开始，尽可能深地探索图的分支，直到达到一个无法继续前进的顶点，然后回溯。在无向图中，DFS 可以通过跟踪访问状态和父节点来检测环路。
以下是一个使用DFS检测无向图环路的Java实现示例：
import java.util.*;
public class UndirectedGraphCycleDetector {
private Map<String, List<String>> adj; // 邻接表表示图
private Set<String> visited; // 记录已访问的节点
private Map<String, String> parent; // 记录节点的父节点
public UndirectedGraphCycleDetector(Map<String, List<String>> graph) {
this.adj = graph;
this.visited = new HashSet<>();
this.parent = new HashMap<>();
}
/**
* 检测图中是否存在环路
* @return 如果存在环路则返回 true，否则返回 false
*/
public boolean hasCycle() {
// 遍历所有顶点，以防图不是连通的
for (String vertex : adj.keySet()) {
if (!visited.contains(vertex)) {
if (dfs(vertex, null)) { // 从未访问的顶点开始DFS，初始父节点为null
return true;
}
}
}
return false;
}
/**
* 深度优先搜索辅助函数
* @param u 当前访问的顶点
* @param p u的父节点
* @return 如果从u开始的路径中存在环路则返回 true，否则返回 false
*/
private boolean dfs(String u, String p) {
visited.add(u); // 标记当前节点已访问
parent.put(u, p); // 记录父节点
// 遍历u的所有邻居
if (adj.containsKey(u)) { // 确保u在图中存在邻居列表
for (String v : adj.get(u)) {
if (!visited.contains(v)) {
// 如果邻居v未被访问，则递归访问v
if (dfs(v, u)) {
return true; // 如果子递归发现环，则返回true
}
} else if (!v.equals(p)) {
// 如果邻居v已被访问，且v不是u的父节点，则发现环路
// (v.equals(p)是为了避免误判通过父节点回溯的情况)
return true;
}
}
}
return false; // 从当前节点出发未发现环路
}
public static void main(String[] args) {
// 示例1: 无环图 (a-b, a-e, c-b, c-d)
Map<String, List<String>> graph1 = new HashMap<>();
graph1.put("a", Arrays.asList("b", "e"));
graph1.put("b", Arrays.asList("a", "c"));
graph1.put("c", Arrays.asList("b", "d"));
graph1.put("d", Arrays.asList("c"));
graph1.put("e", Arrays.asList("a"));
UndirectedGraphCycleDetector detector1 = new UndirectedGraphCycleDetector(graph1);
System.out.println("Graph 1 has cycle: " + detector1.hasCycle()); // Expected: false
// 示例2: 有环图 (a-b, b-c, c-a)
Map<String, List<String>> graph2 = new HashMap<>();
graph2.put("a", Arrays.asList("b", "c"));
graph2.put("b", Arrays.asList("a", "c"));
graph2.put("c", Arrays.asList("a", "b"));
UndirectedGraphCycleDetector detector2 = new UndirectedGraphCycleDetector(graph2);
System.out.println("Graph 2 has cycle: " + detector2.hasCycle()); // Expected: true
// 示例3: 包含孤立节点或非连通分量
Map<String, List<String>> graph3 = new HashMap<>();
graph3.put("x", Arrays.asList("y"));
graph3.put("y", Arrays.asList("x"));
graph3.put("z", new ArrayList<>()); // 孤立节点
graph3.put("p", Arrays.asList("q"));
graph3.put("q", Arrays.asList("p"));
UndirectedGraphCycleDetector detector3 = new UndirectedGraphCycleDetector(graph3);
System.out.println("Graph 3 has cycle: " + detector3.hasCycle()); // Expected: false
}
}并查集（Disjoint Set Union, DSU）是一种用于管理元素分组的数据结构，它支持两种主要操作：find（查找元素所属的集合）和 union（合并两个集合）。在无向图中，并查集可以高效地检测环路。
以下是一个使用并查集检测无向图环路的Java实现示例：
import java.util.*;
public class UndirectedGraphCycleDetectorUnionFind {
// 存储每个元素的父节点
private Map<String, String> parent;
// 存储每个集合的秩（用于优化union操作，减少树的高度）
private Map<String, Integer> rank;
public UndirectedGraphCycleDetectorUnionFind(Set<String> vertices) {
parent = new HashMap<>();
rank = new HashMap<>();
// 初始化：每个顶点都是自己的父节点，秩为0
for (String vertex : vertices) {
parent.put(vertex, vertex);
rank.put(vertex, 0);
}
}
/**
* 查找元素所在集合的代表（根节点），并进行路径压缩
* @param i 要查找的元素
* @return 元素所在集合的代表
*/
private String find(String i) {
if (!parent.get(i).equals(i)) {
// 路径压缩：将i直接连接到其根节点
parent.put(i, find(parent.get(i)));
}
return parent.get(i);
}
/**
* 合并两个元素所在的集合（按秩合并）
* @param i 元素1
* @param j 元素2
* @return 如果成功合并（即i和j原来不在同一个集合中）返回 true，否则返回 false
*/
private 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(rootJ) < rank.get(rootI)) {
parent.put(rootJ, rootI);
} else { // 秩相等时，任意一个作为根，并增加其秩
parent.put(rootJ, rootI);
rank.put(rootI, rank.get(rootI) + 1);
}
return true;
}
return false; // 已经在同一个集合中，合并失败（意味着发现环）
}
/**
* 检测图中是否存在环路
* @param edges 图的边列表，每条边表示为一对字符串 (u, v)
* @return 如果存在环路则返回 true，否则返回 false
*/
public boolean hasCycle(List<String[]> edges) {
for (String[] edge : edges) {
String u = edge[0];
String v = edge[1];
String rootU = find(u);
String rootV = find(v);
if (rootU.equals(rootV)) {
// 如果u和v的根节点相同，说明它们已经在同一个连通分量中，
// 添加这条边会形成环路
return true;
} else {
// 否则，合并u和v所在的集合
union(u, v);
}
}
return false;
}
public static void main(String[] args) {
// 示例1: 无环图 (a-b, a-e, c-b, c-d)
Set<String> vertices1 = new HashSet<>(Arrays.asList("a", "b", "c", "d", "e"));
List<String[]> edges1 = Arrays.asList(
new String[]{"a", "b"},
new String[]{"a", "e"},
new String[]{"c", "b"},
new String[]{"c", "d"}
);
UndirectedGraphCycleDetectorUnionFind detector1 = new UndirectedGraphCycleDetectorUnionFind(vertices1);
System.out.println("Graph 1 has cycle: " + detector1.hasCycle(edges1)); // Expected: false
// 示例2: 有环图 (a-b, b-c, c-a)
Set<String> vertices2 = new HashSet<>(Arrays.asList("a", "b", "c"));
List<String[]> edges2 = Arrays.asList(
new String[]{"a", "b"},
new String[]{"b", "c"},
new String[]{"c", "a"}
);
UndirectedGraphCycleDetectorUnionFind detector2 = new UndirectedGraphCycleDetectorUnionFind(vertices2);
System.out.println("Graph 2 has cycle: " + detector2.hasCycle(edges2)); // Expected: true
// 示例3: 包含孤立节点或非连通分量 (并查集主要关注边，只要边不形成环即可)
Set<String> vertices3 = new HashSet<>(Arrays.asList("x", "y", "z", "p", "q"));
List<String[]> edges3 = Arrays.asList(
new String[]{"x", "y"},
new String[]{"p", "q"}
);
UndirectedGraphCycleDetectorUnionFind detector3 = new UndirectedGraphCycleDetectorUnionFind(vertices3);
System.out.println("Graph 3 has cycle: " + detector3.hasCycle(edges3)); // Expected: false
}
}在无向图中检测环路时，DFS和并查集都是有效的选择。DFS更侧重于图的遍历和路径探索，而并查集则侧重于维护连通分量。根据具体需求和图的特性，可以选择最适合的算法。例如，如果还需要进行其他基于遍历的操作，DFS可能更方便；如果主要关注连通性问题，并查集则更为高效。
以上就是如何检测无向图中的环路的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
998
收藏
