Class StronglyConnectedComponentsUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.StronglyConnectedComponentsUtil
public final class StronglyConnectedComponentsUtil extends Object
Strongly Connected Components Util - Tarjan's Algorithm 强连通分量工具类 - Tarjan算法

Utility class for finding strongly connected components (SCCs) in directed graphs using Tarjan's algorithm. For undirected graphs, returns connected components.

使用Tarjan算法在有向图中查找强连通分量(SCC)的工具类。对于无向图，返回连通分量。

Features | 主要功能:

  • Find all SCCs - 查找所有强连通分量
  • Count SCCs - 统计强连通分量数量
  • Find SCC containing a specific vertex - 查找包含特定顶点的强连通分量
  • Check if graph is strongly connected - 检查图是否强连通
  • Build condensation graph (DAG of SCCs) - 构建缩合图（强连通分量的有向无环图）

Usage Examples | 使用示例:

Graph<String> graph = new DirectedGraph<>();
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");

List<Set<String>> sccs = StronglyConnectedComponentsUtil.find(graph);
boolean strong = StronglyConnectedComponentsUtil.isStronglyConnected(graph);

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty results for null graph, throws for null vertex) - 空值安全: 是

Performance | 性能特性:

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

  • Method Details

    • find

      public static <V> List<Set<V>> find(Graph<V> graph)
      Find all strongly connected components using Tarjan's algorithm. For undirected graphs, returns connected components. 使用Tarjan算法查找所有强连通分量。对于无向图，返回连通分量。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      list of SCCs (each SCC is a set of vertices) | 强连通分量列表（每个分量是顶点集合）

    • count

      public static <V> int count(Graph<V> graph)
      Count the number of strongly connected components. 统计强连通分量的数量。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      number of SCCs | 强连通分量数量

    • componentOf

      public static <V> Set<V> componentOf(Graph<V> graph, V vertex)
      Find the SCC containing the given vertex. 查找包含给定顶点的强连通分量。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      vertex - the vertex to find | 要查找的顶点
      Returns:
      the SCC containing the vertex | 包含该顶点的强连通分量
      Throws:
      InvalidVertexException - if vertex is null | 当顶点为null时抛出

    • isStronglyConnected

      public static <V> boolean isStronglyConnected(Graph<V> graph)
      Check if the entire graph is strongly connected. 检查整个图是否为强连通。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      true if the graph is strongly connected | 如果图是强连通的返回true

    • condensation

      public static <V> Graph<Set<V>> condensation(Graph<V> graph)
      Build the condensation graph (DAG of SCCs). Each vertex in the result is a Set representing an SCC. 构建缩合图（强连通分量的有向无环图）。结果中每个顶点是一个表示SCC的集合。
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      condensation graph (DAG) | 缩合图（有向无环图）