java.lang.Object

cloud.opencode.base.collections.graph.GraphTraversalUtil

public final class GraphTraversalUtil extends Object

GraphTraversalUtil - Graph Traversal Utilities GraphTraversalUtil - 图遍历工具类

Provides common graph traversal algorithms including BFS, DFS, topological sort, etc.

提供常见的图遍历算法，包括 BFS、DFS、拓扑排序等。

Features | 主要功能:

Breadth-first search (BFS) - 广度优先搜索
Depth-first search (DFS) - 深度优先搜索
Topological sort - 拓扑排序
Cycle detection - 环检测
Path finding - 路径查找
Connected components - 连通分量

Usage Examples | 使用示例:

MutableGraph<String> graph = MutableGraph.directed();
graph.putEdge("A", "B");
graph.putEdge("B", "C");
graph.putEdge("A", "C");

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

// DFS traversal
List<String> dfsOrder = GraphTraversalUtil.dfs(graph, "A");

// Topological sort
List<String> topoOrder = GraphTraversalUtil.topologicalSort(graph);

// Check for cycles
boolean hasCycle = GraphTraversalUtil.hasCycle(graph);

// Find shortest path
List<String> path = GraphTraversalUtil.shortestPath(graph, "A", "C");

Performance | 性能特性:

BFS/DFS: O(V + E) - BFS/DFS: O(V + E)
Topological sort: O(V + E) - 拓扑排序: O(V + E)
Cycle detection: O(V + E) - 环检测: O(V + E)

Security | 安全性:

Thread-safe: No (depends on graph) - 线程安全: 否（取决于图）
Null-safe: No (nulls not allowed) - 空值安全: 否（不允许空值）

Since:

JDK 25, opencode-base-collections V1.0.0

Author:

Leon Soo www.LeonSoo.com

See Also:

Method Summary

Modifier and Type

Method

Description

static <N> List<List<N>>

allPaths(Graph<N> graph, N source, N target, int maxDepth)

Find all paths between two nodes (limited by max depth).

static <N> List<N>

bfs(Graph<N> graph, N startNode)

Perform breadth-first search starting from the given node.

static <N> void

bfs(Graph<N> graph, N startNode, Consumer<N> visitor)

Perform BFS with a visitor function.

static <N> Optional<N>

bfsUntil(Graph<N> graph, N startNode, Predicate<N> condition)

Perform BFS until a condition is met.

static <N> List<Set<N>>

connectedComponents(Graph<N> graph)

Find all connected components in an undirected graph.

static <N> List<N>

dfs(Graph<N> graph, N startNode)

Perform depth-first search starting from the given node.

static <N> void

dfs(Graph<N> graph, N startNode, Consumer<N> visitor)

Perform DFS with a visitor function.

static <N> List<N>

dfsIterative(Graph<N> graph, N startNode)

Perform iterative depth-first search.

static <N> Map<N,Double>

dijkstra(ValueGraph<N, ? extends Number> graph, N source)

Computes shortest distances from source to all reachable nodes using Dijkstra's algorithm.

static <N> boolean

hasCycle(Graph<N> graph)

Check if the graph has a cycle.

static <N> boolean

hasPath(Graph<N> graph, N source, N target)

Check if there is a path between two nodes.

static <N> boolean

isConnected(Graph<N> graph)

Check if the graph is connected (for undirected graphs).

static <N> boolean

isDag(Graph<N> graph)

Check if the graph is a DAG (Directed Acyclic Graph).

static <N> Set<N>

reachableFrom(Graph<N> graph, N startNode)

Get all reachable nodes from a starting node.

static <N> Optional<List<N>>

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

Find the shortest path between two nodes using BFS.

static <N> List<N>

shortestWeightedPath(ValueGraph<N, ? extends Number> graph, N source, N target)

Finds the shortest path from source to target using Dijkstra's algorithm.

static <N> List<Set<N>>

stronglyConnectedComponents(Graph<N> graph)

Find all strongly connected components in a directed graph (Kosaraju's algorithm).

static <N> List<N>

topologicalSort(Graph<N> graph)

Perform topological sort on a directed acyclic graph (DAG).

static <N> Optional<List<N>>

topologicalSortKahn(Graph<N> graph)

Perform topological sort using Kahn's algorithm.

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

Method Details
- bfs
  
  public static <N> List<N> bfs(Graph<N> graph, N startNode)
  
  Perform breadth-first search starting from the given node. 从给定节点开始执行广度优先搜索。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  Returns:
  
  nodes in BFS order | BFS 顺序的节点
- bfs
  
  public static <N> void bfs(Graph<N> graph, N startNode, Consumer<N> visitor)
  
  Perform BFS with a visitor function. 使用访问者函数执行 BFS。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  visitor - the visitor function | 访问者函数
- bfsUntil
  
  public static <N> Optional<N> bfsUntil(Graph<N> graph, N startNode, Predicate<N> condition)
  
  Perform BFS until a condition is met. 执行 BFS 直到满足条件。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  condition - the stop condition | 停止条件
  
  Returns:
  
  the first node matching condition, or empty | 第一个匹配条件的节点，或空
- dfs
  
  public static <N> List<N> dfs(Graph<N> graph, N startNode)
  
  Perform depth-first search starting from the given node. 从给定节点开始执行深度优先搜索。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  Returns:
  
  nodes in DFS order | DFS 顺序的节点
- dfsIterative
  
  public static <N> List<N> dfsIterative(Graph<N> graph, N startNode)
  
  Perform iterative depth-first search. 执行迭代式深度优先搜索。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  Returns:
  
  nodes in DFS order | DFS 顺序的节点
- dfs
  
  public static <N> void dfs(Graph<N> graph, N startNode, Consumer<N> visitor)
  
  Perform DFS with a visitor function. 使用访问者函数执行 DFS。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  visitor - the visitor function | 访问者函数
- topologicalSort
  
  public static <N> List<N> topologicalSort(Graph<N> graph)
  
  Perform topological sort on a directed acyclic graph (DAG). 在有向无环图 (DAG) 上执行拓扑排序。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  nodes in topological order | 拓扑顺序的节点
  
  Throws:
  
  IllegalArgumentException - if graph has a cycle | 如果图有环则抛出异常
- topologicalSortKahn
  
  public static <N> Optional<List<N>> topologicalSortKahn(Graph<N> graph)
  
  Perform topological sort using Kahn's algorithm. 使用 Kahn 算法执行拓扑排序。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  nodes in topological order, or empty if cycle exists | 拓扑顺序的节点，如果有环则返回空
- hasCycle
  
  public static <N> boolean hasCycle(Graph<N> graph)
  
  Check if the graph has a cycle. 检查图是否有环。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  true if has cycle | 如果有环则返回 true
- shortestPath
  
  public static <N> Optional<List<N>> shortestPath(Graph<N> graph, N source, N target)
  
  Find the shortest path between two nodes using BFS. 使用 BFS 找到两个节点之间的最短路径。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source node | 源节点
  
  target - the target node | 目标节点
  
  Returns:
  
  the shortest path, or empty if no path exists | 最短路径，如果不存在则返回空
- hasPath
  
  public static <N> boolean hasPath(Graph<N> graph, N source, N target)
  
  Check if there is a path between two nodes. 检查两个节点之间是否有路径。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source node | 源节点
  
  target - the target node | 目标节点
  
  Returns:
  
  true if path exists | 如果路径存在则返回 true
- allPaths
  
  public static <N> List<List<N>> allPaths(Graph<N> graph, N source, N target, int maxDepth)
  
  Find all paths between two nodes (limited by max depth). 找到两个节点之间的所有路径（受最大深度限制）。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  source - the source node | 源节点
  
  target - the target node | 目标节点
  
  maxDepth - maximum path depth | 最大路径深度
  
  Returns:
  
  all paths | 所有路径
- connectedComponents
  
  public static <N> List<Set<N>> connectedComponents(Graph<N> graph)
  
  Find all connected components in an undirected graph. 找到无向图中的所有连通分量。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  list of connected components | 连通分量列表
- stronglyConnectedComponents
  
  public static <N> List<Set<N>> stronglyConnectedComponents(Graph<N> graph)
  
  Find all strongly connected components in a directed graph (Kosaraju's algorithm). 使用 Kosaraju 算法找到有向图中的所有强连通分量。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  list of strongly connected components | 强连通分量列表
- reachableFrom
  
  public static <N> Set<N> reachableFrom(Graph<N> graph, N startNode)
  
  Get all reachable nodes from a starting node. 获取从起始节点可达的所有节点。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  startNode - the starting node | 起始节点
  
  Returns:
  
  set of reachable nodes | 可达节点集合
- isConnected
  
  public static <N> boolean isConnected(Graph<N> graph)
  
  Check if the graph is connected (for undirected graphs). 检查图是否连通（针对无向图）。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  true if connected | 如果连通则返回 true
- isDag
  
  public static <N> boolean isDag(Graph<N> graph)
  
  Check if the graph is a DAG (Directed Acyclic Graph). 检查图是否是 DAG（有向无环图）。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  true if DAG | 如果是 DAG 则返回 true
- dijkstra
  
  public static <N> Map<N,Double> dijkstra(ValueGraph<N, ? extends Number> graph, N source)
  
  Computes shortest distances from source to all reachable nodes using Dijkstra's algorithm. 使用 Dijkstra 算法计算从源节点到所有可达节点的最短距离。
  The graph edge values must be non-negative numbers. If a negative weight edge is encountered, an IllegalArgumentException is thrown.
  
  图的边值必须为非负数。如果遇到负权边，将抛出 IllegalArgumentException。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the value graph | 值图
  
  source - the source node | 源节点
  
  Returns:
  
  map of node to shortest distance from source | 节点到源节点最短距离的映射
  
  Throws:
  
  IllegalArgumentException - if a negative weight edge is found | 如果发现负权边则抛出异常
  
  Since:
  
  JDK 25, opencode-base-collections V1.0.3
- shortestWeightedPath
  
  public static <N> List<N> shortestWeightedPath(ValueGraph<N, ? extends Number> graph, N source, N target)
  
  Finds the shortest path from source to target using Dijkstra's algorithm. 使用 Dijkstra 算法查找从源到目标的最短路径。
  Returns the path as a list of nodes from source to target (inclusive). Returns an empty list if the target is unreachable.
  
  返回从源到目标的节点列表（包含两端）。如果目标不可达则返回空列表。
  
  Type Parameters:
  
  N - node type | 节点类型
  
  Parameters:
  
  graph - the value graph | 值图
  
  source - the source node | 源节点
  
  target - the target node | 目标节点
  
  Returns:
  
  path as list of nodes, or empty list if unreachable | 节点路径列表，不可达则返回空列表
  
  Throws:
  
  IllegalArgumentException - if a negative weight edge is found | 如果发现负权边则抛出异常
  
  Since:
  
  JDK 25, opencode-base-collections V1.0.3

Class GraphTraversalUtil

Method Summary

Methods inherited from class Object

Method Details

bfs

bfs

bfsUntil

dfs

dfsIterative

dfs

topologicalSort

topologicalSortKahn

hasCycle

shortestPath

hasPath

allPaths

connectedComponents

stronglyConnectedComponents

reachableFrom

isConnected

isDag

dijkstra

shortestWeightedPath