Class ArticulationPointUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.ArticulationPointUtil
public final class ArticulationPointUtil extends Object
Articulation Point and Bridge Finder Utility 割点与桥查找工具类

Finds articulation points (cut vertices) and bridges (cut edges) in a graph using Tarjan's algorithm with iterative DFS to avoid stack overflow on large graphs.

使用Tarjan算法和迭代DFS在图中查找割点（关节点）和桥（割边）， 避免大图上的栈溢出。

Features | 主要功能:

  • Find all articulation points (cut vertices) - 查找所有割点
  • Find all bridges (cut edges) - 查找所有桥
  • Check if graph is biconnected - 检查图是否双连通
  • Iterative DFS for stack safety - 迭代DFS保证栈安全
  • Directed graphs treated as undirected - 有向图按无向图处理

Usage Examples | 使用示例:

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

Set<String> articulationPoints = ArticulationPointUtil.findArticulationPoints(graph);
// articulationPoints = {"B"}

Set<Edge<String>> bridges = ArticulationPointUtil.findBridges(graph);
// bridges = {A->B, B->C}

boolean biconnected = ArticulationPointUtil.isBiconnected(graph);
// biconnected = false

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

    • findArticulationPoints

      public static <V> Set<V> findArticulationPoints(Graph<V> graph)
      Find all articulation points (cut vertices) in the graph. 查找图中的所有割点（关节点）。

      For directed graphs, edges are treated as undirected.

      对于有向图，边按无向处理。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph to analyze | 要分析的图
      Returns:
      set of articulation points, or empty set if null graph | 割点集合，null图返回空集

    • findBridges

      public static <V> Set<Edge<V>> findBridges(Graph<V> graph)
      Find all bridges (cut edges) in the graph. 查找图中的所有桥（割边）。

      For directed graphs, edges are treated as undirected.

      对于有向图，边按无向处理。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph to analyze | 要分析的图
      Returns:
      set of bridge edges, or empty set if null graph | 桥边集合，null图返回空集

    • isBiconnected

      public static <V> boolean isBiconnected(Graph<V> graph)
      Check if the graph is biconnected. 检查图是否双连通。

      A graph is biconnected if it is connected, has at least 2 vertices, and has no articulation points.

      如果图是连通的、至少有2个顶点且没有割点，则图是双连通的。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph to check | 要检查的图
      Returns:
      true if graph is biconnected | 如果图是双连通的返回true