java.lang.Object

cloud.opencode.base.graph.OpenGraph

public final class OpenGraph extends Object

Open Graph 图组件入口类

Main entry point for graph operations.

图操作的主要入口点。

Features | 特性:

Graph creation (directed/undirected) | 图创建（有向/无向）
Graph traversal (BFS/DFS) | 图遍历（BFS/DFS）
Shortest path (Dijkstra/A*) | 最短路径（Dijkstra/A*）
Topological sort | 拓扑排序
Connectivity analysis | 连通性分析

Usage Examples | 使用示例:

// Create a directed graph
Graph<String> graph = OpenGraph.directed();
graph.addEdge("A", "B", 1.0);
graph.addEdge("B", "C", 2.0);

// BFS traversal
List<String> bfsResult = OpenGraph.bfs(graph, "A");

// Shortest path
List<String> path = OpenGraph.shortestPath(graph, "A", "C");

// Topological sort
List<String> order = OpenGraph.topologicalSort(graph);

Security | 安全性:

Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
Null-safe: Yes (delegates to null-safe implementations) - 空值安全: 是（委托给空值安全的实现）

Since:

JDK 25, opencode-base-graph V1.0.0

Author:

Leon Soo www.LeonSoo.com

See Also:

Method Summary

Modifier and Type

Method

Description

static <V> List<V>

aStar(Graph<V> graph, V source, V target, BiFunction<V,V,Double> heuristic)

Find shortest path using A* algorithm 使用A*算法查找最短路径

static <V> List<V>

bfs(Graph<V> graph, V start)

Breadth-first search 广度优先搜索

static <V> List<V>

bidirectionalBfs(Graph<V> graph, V source, V target)

Find path using bidirectional BFS (efficient for large graphs) 使用双向BFS查找路径（对大图高效）

static <V> boolean

canTopologicalSort(Graph<V> graph)

Check if topological sort is possible (graph is DAG) 检查是否可以进行拓扑排序（图是DAG）

static <V> NetworkFlowUtil.FlowResult<V>

computeFlow(Graph<V> graph, V source, V sink)

Compute flow result with detailed information 计算包含详细信息的流结果

static <V> int

connectedComponentCount(Graph<V> graph)

Get the number of connected components 获取连通分量数量

static <V> List<Set<V>>

connectedComponents(Graph<V> graph)

Find all connected components 查找所有连通分量

static <V> List<V>

dfs(Graph<V> graph, V start)

Depth-first search 深度优先搜索

static <V> List<V>

dfsIterative(Graph<V> graph, V start)

Safe iterative depth-first search (avoids stack overflow) 安全的迭代式深度优先搜索（避免栈溢出）

static <V> Map<V,Double>

dijkstra(Graph<V> graph, V source)

Dijkstra's shortest path algorithm Dijkstra最短路径算法

static <V> Graph<V>

directed()

Create a directed graph 创建有向图

static <V> GraphBuilder<V>

directedBuilder()

Create a graph builder for directed graph 创建有向图构建器

static <V> WeightedGraph<V>

directedWeighted()

Create a directed weighted graph 创建有向加权图

static <V> List<V>

findCycle(Graph<V> graph)

Find one cycle if exists 如果存在则找到一个环

static <V> Map<Edge<V>,Double>

getFlows(Graph<V> graph, V source, V sink)

Get flow on each edge 获取每条边上的流量

static <V> boolean

hasCycle(Graph<V> graph)

Check if graph contains a cycle 检查图是否包含环

static <V> boolean

hasSpanningTree(Graph<V> graph)

Check if a graph has a spanning tree (is connected) 检查图是否有生成树（是否连通）

static <V> boolean

isConnected(Graph<V> graph, V v1, V v2)

Check if two vertices are connected 检查两个顶点是否连通

static <V> boolean

isFullyConnected(Graph<V> graph)

Check if graph is fully connected 检查图是否完全连通

static <V> Set<Edge<V>>

kruskal(Graph<V> graph)

Find minimum spanning tree using Kruskal's algorithm 使用Kruskal算法查找最小生成树

static <V> double

maxFlow(Graph<V> graph, V source, V sink)

Calculate maximum flow using Ford-Fulkerson algorithm (Edmonds-Karp) 使用Ford-Fulkerson算法（Edmonds-Karp）计算最大流

static <V> Set<Edge<V>>

minCut(Graph<V> graph, V source, V sink)

Find minimum cut edges 查找最小割边

static <V> double

mstWeight(Graph<V> graph)

Calculate the total weight of the minimum spanning tree 计算最小生成树的总权重

static <V> Set<Edge<V>>

prim(Graph<V> graph)

Find minimum spanning tree using Prim's algorithm 使用Prim算法查找最小生成树

static <V> Set<Edge<V>>

prim(Graph<V> graph, V start)

Find minimum spanning tree using Prim's algorithm starting from a vertex 使用Prim算法从指定顶点开始查找最小生成树

static <V> List<V>

shortestPath(Graph<V> graph, V source, V target)

Find shortest path between two vertices 查找两个顶点之间的最短路径

static <V> List<V>

topologicalSort(Graph<V> graph)

Topological sort using Kahn's algorithm 使用Kahn算法进行拓扑排序

static <V> Graph<V>

undirected()

Create an undirected graph 创建无向图

static <V> GraphBuilder<V>

undirectedBuilder()

Create a graph builder for undirected graph 创建无向图构建器

static <V> WeightedGraph<V>

undirectedWeighted()

Create an undirected weighted graph 创建无向加权图

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details
- directed
  
  public static <V> Graph<V> directed()
  
  Create a directed graph 创建有向图
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Returns:
  
  a new directed graph | 新的有向图
- undirected
  
  public static <V> Graph<V> undirected()
  
  Create an undirected graph 创建无向图
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Returns:
  
  a new undirected graph | 新的无向图
- directedWeighted
  
  public static <V> WeightedGraph<V> directedWeighted()
  
  Create a directed weighted graph 创建有向加权图
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Returns:
  
  a new directed weighted graph | 新的有向加权图
- undirectedWeighted
  
  public static <V> WeightedGraph<V> undirectedWeighted()
  
  Create an undirected weighted graph 创建无向加权图
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Returns:
  
  a new undirected weighted graph | 新的无向加权图
- directedBuilder
  
  public static <V> GraphBuilder<V> directedBuilder()
  
  Create a graph builder for directed graph 创建有向图构建器
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Returns:
  
  a new graph builder | 新的图构建器
- undirectedBuilder
  
  public static <V> GraphBuilder<V> undirectedBuilder()
  
  Create a graph builder for undirected graph 创建无向图构建器
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Returns:
  
  a new graph builder | 新的图构建器
- bfs
  
  public static <V> List<V> bfs(Graph<V> graph, V start)
  
  Breadth-first search 广度优先搜索
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph to traverse | 要遍历的图
  
  start - the starting vertex | 起始顶点
  
  Returns:
  
  list of vertices in BFS order | BFS顺序的顶点列表
- dfs
  
  public static <V> List<V> dfs(Graph<V> graph, V start)
  
  Depth-first search 深度优先搜索
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph to traverse | 要遍历的图
  
  start - the starting vertex | 起始顶点
  
  Returns:
  
  list of vertices in DFS order | DFS顺序的顶点列表
- dfsIterative
  
  public static <V> List<V> dfsIterative(Graph<V> graph, V start)
  
  Safe iterative depth-first search (avoids stack overflow) 安全的迭代式深度优先搜索（避免栈溢出）
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph to traverse | 要遍历的图
  
  start - the starting vertex | 起始顶点
  
  Returns:
  
  list of vertices in DFS order | DFS顺序的顶点列表
- dijkstra
  
  public static <V> Map<V,Double> dijkstra(Graph<V> graph, V source)
  
  Dijkstra's shortest path algorithm Dijkstra最短路径算法
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source vertex | 源顶点
  
  Returns:
  
  map of vertex to shortest distance from source | 顶点到源的最短距离映射
- shortestPath
  
  public static <V> List<V> shortestPath(Graph<V> graph, V source, V target)
  
  Find shortest path between two vertices 查找两个顶点之间的最短路径
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source vertex | 源顶点
  
  target - the target vertex | 目标顶点
  
  Returns:
  
  list of vertices in the shortest path | 最短路径的顶点列表
- aStar
  
  public static <V> List<V> aStar(Graph<V> graph, V source, V target, BiFunction<V,V,Double> heuristic)
  
  Find shortest path using A* algorithm 使用A*算法查找最短路径
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source vertex | 源顶点
  
  target - the target vertex | 目标顶点
  
  heuristic - the heuristic function | 启发式函数
  
  Returns:
  
  list of vertices in the shortest path | 最短路径的顶点列表
- bidirectionalBfs
  
  public static <V> List<V> bidirectionalBfs(Graph<V> graph, V source, V target)
  
  Find path using bidirectional BFS (efficient for large graphs) 使用双向BFS查找路径（对大图高效）
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source vertex | 源顶点
  
  target - the target vertex | 目标顶点
  
  Returns:
  
  list of vertices in the path | 路径的顶点列表
- topologicalSort
  
  public static <V> List<V> topologicalSort(Graph<V> graph)
  
  Topological sort using Kahn's algorithm 使用Kahn算法进行拓扑排序
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the directed graph | 有向图
  
  Returns:
  
  list of vertices in topological order | 拓扑顺序的顶点列表
- canTopologicalSort
  
  public static <V> boolean canTopologicalSort(Graph<V> graph)
  
  Check if topological sort is possible (graph is DAG) 检查是否可以进行拓扑排序（图是DAG）
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  true if topological sort is possible | 如果可以进行拓扑排序返回true
- 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 | 形成环的顶点列表
- connectedComponents
  
  public static <V> List<Set<V>> connectedComponents(Graph<V> graph)
  
  Find all connected components 查找所有连通分量
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  list of connected components | 连通分量列表
- 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 检查图是否完全连通
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  true if fully connected | 如果完全连通返回true
- connectedComponentCount
  
  public static <V> int connectedComponentCount(Graph<V> graph)
  
  Get the number of connected components 获取连通分量数量
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  number of connected components | 连通分量数量
- prim
  
  public static <V> Set<Edge<V>> prim(Graph<V> graph)
  
  Find minimum spanning tree using Prim's algorithm 使用Prim算法查找最小生成树
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the undirected graph | 无向图
  
  Returns:
  
  set of edges in the MST | 最小生成树的边集合
- prim
  
  public static <V> Set<Edge<V>> prim(Graph<V> graph, V start)
  
  Find minimum spanning tree using Prim's algorithm starting from a vertex 使用Prim算法从指定顶点开始查找最小生成树
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the undirected graph | 无向图
  
  start - the starting vertex | 起始顶点
  
  Returns:
  
  set of edges in the MST | 最小生成树的边集合
- kruskal
  
  public static <V> Set<Edge<V>> kruskal(Graph<V> graph)
  
  Find minimum spanning tree using Kruskal's algorithm 使用Kruskal算法查找最小生成树
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the undirected graph | 无向图
  
  Returns:
  
  set of edges in the MST | 最小生成树的边集合
- mstWeight
  
  public static <V> double mstWeight(Graph<V> graph)
  
  Calculate the total weight of the minimum spanning tree 计算最小生成树的总权重
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the undirected graph | 无向图
  
  Returns:
  
  total weight of MST | 最小生成树的总权重
- hasSpanningTree
  
  public static <V> boolean hasSpanningTree(Graph<V> graph)
  
  Check if a graph has a spanning tree (is connected) 检查图是否有生成树（是否连通）
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  true if graph is connected | 如果图连通返回true
- maxFlow
  
  public static <V> double maxFlow(Graph<V> graph, V source, V sink)
  
  Calculate maximum flow using Ford-Fulkerson algorithm (Edmonds-Karp) 使用Ford-Fulkerson算法（Edmonds-Karp）计算最大流
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the directed graph with edge weights as capacities | 边权重作为容量的有向图
  
  source - the source vertex | 源顶点
  
  sink - the sink vertex | 汇顶点
  
  Returns:
  
  the maximum flow value | 最大流值
- getFlows
  
  public static <V> Map<Edge<V>,Double> getFlows(Graph<V> graph, V source, V sink)
  
  Get flow on each edge 获取每条边上的流量
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the directed graph | 有向图
  
  source - the source vertex | 源顶点
  
  sink - the sink vertex | 汇顶点
  
  Returns:
  
  map of edge to flow value | 边到流量值的映射
- minCut
  
  public static <V> Set<Edge<V>> minCut(Graph<V> graph, V source, V sink)
  
  Find minimum cut edges 查找最小割边
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the directed graph | 有向图
  
  source - the source vertex | 源顶点
  
  sink - the sink vertex | 汇顶点
  
  Returns:
  
  set of edges in the minimum cut | 最小割中的边集合
- computeFlow
  
  public static <V> NetworkFlowUtil.FlowResult<V> computeFlow(Graph<V> graph, V source, V sink)
  
  Compute flow result with detailed information 计算包含详细信息的流结果
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the directed graph | 有向图
  
  source - the source vertex | 源顶点
  
  sink - the sink vertex | 汇顶点
  
  Returns:
  
  the flow result with max flow, edge flows, and min-cut | 包含最大流、边流量和最小割的流结果

Class OpenGraph

Method Summary

Methods inherited from class Object

Method Details

directed

undirected

directedWeighted

undirectedWeighted

directedBuilder

undirectedBuilder

bfs

dfs

dfsIterative

dijkstra

shortestPath

aStar

bidirectionalBfs

topologicalSort

canTopologicalSort

hasCycle

findCycle

connectedComponents

isConnected

isFullyConnected

connectedComponentCount

prim

prim

kruskal

mstWeight

hasSpanningTree

maxFlow

getFlows

minCut

computeFlow