Class CycleDetectionUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.CycleDetectionUtil
public final class CycleDetectionUtil extends Object
Cycle Detection Util 环检测工具类

Utility class for detecting cycles in graphs.

图中环检测的工具类。

Algorithms | 算法:

  • DFS coloring for directed graphs | 有向图的DFS着色算法
  • Union-Find for undirected graphs | 无向图的并查集算法

Time Complexity | 时间复杂度: O(V + E)

Features | 主要功能:

  • DFS coloring cycle detection for directed graphs - 有向图的DFS着色环检测
  • Union-find cycle detection for undirected graphs - 无向图的并查集环检测
  • Cycle path extraction - 环路径提取

Usage Examples | 使用示例:

// Check if graph has a cycle
boolean hasCycle = CycleDetectionUtil.hasCycle(graph);

// Find one cycle if exists
List<String> cycle = CycleDetectionUtil.findCycle(graph);

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns false/empty for null inputs) - 空值安全: 是（null输入返回false/空）

Performance | 性能特性:

  • Time complexity: O(V + E) - 时间复杂度: O(V + E)
  • Space complexity: O(V) - 空间复杂度: O(V)
Since:
JDK 25, opencode-base-graph V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • hasCycle

      public static <V> boolean hasCycle(Graph<V> graph)
      Check if graph contains a cycle 检查图是否包含环
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      true if graph contains a cycle | 如果图包含环返回true

    • findCycle

      public static <V> List<V> findCycle(Graph<V> graph)
      Find one cycle if exists 如果存在环则找到一个
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      list of vertices forming a cycle, or empty list if no cycle | 形成环的顶点列表，无环时返回空列表

    • wouldCreateCycle

      public static <V> boolean wouldCreateCycle(Graph<V> graph, V from, V to)
      Check if adding an edge would create a cycle 检查添加边是否会创建环

      For directed graphs, checks if there's a directed path from 'to' to 'from'. For undirected graphs, checks if 'from' and 'to' are already connected.

      对于有向图，检查是否存在从 'to' 到 'from' 的有向路径。 对于无向图，检查 'from' 和 'to' 是否已连通。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      from - source vertex | 源顶点
      to - target vertex | 目标顶点
      Returns:
      true if adding the edge would create a cycle | 如果添加边会创建环返回true