Class ConnectedComponentsUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.ConnectedComponentsUtil
public final class ConnectedComponentsUtil extends Object
Connected Components Util 连通分量工具类

Utility class for finding connected components in graphs.

查找图中连通分量的工具类。

Features | 特性:

  • Find all connected components | 查找所有连通分量
  • Check if two vertices are connected | 检查两个顶点是否连通
  • Check if graph is fully connected | 检查图是否完全连通

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

Usage Examples | 使用示例:

// Find all connected components
List<Set<String>> components = ConnectedComponentsUtil.find(graph);

// Check if two vertices are connected
boolean connected = ConnectedComponentsUtil.isConnected(graph, "A", "B");

// Check if graph is fully connected
boolean fullyConnected = ConnectedComponentsUtil.isFullyConnected(graph);

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty/false 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

    • find

      public static <V> List<Set<V>> find(Graph<V> graph)
      Find all connected components 查找所有连通分量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      list of connected components (each component is a set of vertices) | 连通分量列表（每个分量是顶点集合）

    • isConnected

      public static <V> boolean isConnected(Graph<V> graph, V v1, V v2)
      Check if two vertices are connected 检查两个顶点是否连通
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      v1 - first vertex | 第一个顶点
      v2 - second vertex | 第二个顶点
      Returns:
      true if connected | 如果连通返回true

    • isFullyConnected

      public static <V> boolean isFullyConnected(Graph<V> graph)
      Check if graph is fully connected (single component) 检查图是否完全连通（单一分量）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      true if fully connected | 如果完全连通返回true

    • count

      public static <V> int count(Graph<V> graph)
      Get the number of connected components 获取连通分量的数量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      number of connected components | 连通分量数量

    • getLargestComponent

      public static <V> Set<V> getLargestComponent(Graph<V> graph)
      Get the largest connected component 获取最大连通分量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      the largest connected component, or empty set if graph is empty | 最大连通分量，图为空时返回空集合

    • getSmallestComponent

      public static <V> Set<V> getSmallestComponent(Graph<V> graph)
      Get the smallest connected component 获取最小连通分量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      the smallest connected component, or empty set if graph is empty | 最小连通分量，图为空时返回空集合

    • getComponentContaining

      public static <V> Set<V> getComponentContaining(Graph<V> graph, V vertex)
      Get the component containing a specific vertex 获取包含特定顶点的分量
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      vertex - the vertex | 顶点
      Returns:
      the component containing the vertex, or empty set if vertex not found | 包含该顶点的分量，顶点未找到时返回空集合