检测 Java 图中是否存在环

1. 概述

在本教程中，我们将学习如何检测一个有向图中是否存在环。这在图算法中是一个经典问题，尤其在拓扑排序、任务调度等场景中非常常见。

2. 图的表示方式

我们采用邻接表来表示图，这是在 Java 中实现图结构时最常用的方式之一。

首先，我们定义一个 Vertex 类来表示图中的一个顶点：

public class Vertex {

    private String label;
    private boolean beingVisited;
    private boolean visited;
    private List<Vertex> adjacencyList;

    public Vertex(String label) {
        this.label = label;
        this.adjacencyList = new ArrayList<>();
    }

    public void addNeighbor(Vertex adjacent) {
        this.adjacencyList.add(adjacent);
    }
    // getters and setters
}

📌 关键点：

adjacencyList 保存该顶点的所有邻接顶点
beingVisited 表示当前顶点是否正在被访问
visited 表示该顶点是否已经被完全访问过

接着，我们定义 Graph 类来管理整个图：

public class Graph {

    private List<Vertex> vertices;

    public Graph() {
        this.vertices = new ArrayList<>();
    }

    public void addVertex(Vertex vertex) {
        this.vertices.add(vertex);
    }

    public void addEdge(Vertex from, Vertex to) {
        from.addNeighbor(to);
    }

   // ...
}

通过 addVertex() 和 addEdge() 方法，我们可以构建图的结构。

3. 环检测算法

要检测图中是否存在环，我们使用深度优先搜索（DFS）的变种来实现：

✅ 算法思路如下：

从一个未访问的顶点开始，标记为“正在访问”（beingVisited = true）
遍历该顶点的所有邻居：
- 如果某个邻居正在被访问，说明存在环（backward edge）
- 如果邻居未被访问，则递归检查
回溯：将当前顶点标记为“已访问”（visited = true），并取消“正在访问”状态

✅ Java 实现如下：

public boolean hasCycle(Vertex sourceVertex) {
    sourceVertex.setBeingVisited(true);

    for (Vertex neighbor : sourceVertex.getAdjacencyList()) {
        if (neighbor.isBeingVisited()) {
            // 发现回边，说明有环
            return true;
        } else if (!neighbor.isVisited() && hasCycle(neighbor)) {
            return true;
        }
    }

    sourceVertex.setBeingVisited(false);
    sourceVertex.setVisited(true);
    return false;
}

✅ 对于非连通图的处理：

如果图是非连通的，我们需要遍历所有顶点，确保每个连通分量都被检查到：

public boolean hasCycle() {
    for (Vertex vertex : vertices) {
        if (!vertex.isVisited() && hasCycle(vertex)) {
            return true;
        }
    }
    return false;
}

⚠️ 踩坑提醒：如果没有这个包装方法，那么在非连通图中可能会漏检某些子图中的环。

4. 示例测试

我们以一个有环的有向图为例：

我们可以构建这个图并编写一个 JUnit 测试来验证：

@Test
void givenGraph_whenCycleExists_thenReturnTrue() {

    Vertex vertexA = new Vertex("A");
    Vertex vertexB = new Vertex("B");
    Vertex vertexC = new Vertex("C");
    Vertex vertexD = new Vertex("D");

    Graph graph = new Graph();
    graph.addVertex(vertexA);
    graph.addVertex(vertexB);
    graph.addVertex(vertexC);
    graph.addVertex(vertexD);

    graph.addEdge(vertexA, vertexB);
    graph.addEdge(vertexB, vertexC);
    graph.addEdge(vertexC, vertexA);
    graph.addEdge(vertexD, vertexC);

    assertTrue(graph.hasCycle());
}

✅ 测试通过，说明我们的环检测逻辑是正确的。

5. 总结

本教程我们介绍了如何在 Java 中判断一个有向图是否存在环。核心思路是使用 DFS 的变种，通过标记访问状态来识别回边，从而判断是否存在环。

📌 小结：

使用邻接表表示图结构，简洁高效
DFS 是检测环的核心算法
注意处理非连通图的情况
两个布尔标记 beingVisited 和 visited 是关键

如需扩展，可尝试将其用于无向图或结合拓扑排序进行任务调度检测。

Persistence

REST

Security