Class BidirectionalBfsUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.BidirectionalBfsUtil
public final class BidirectionalBfsUtil extends Object
Bidirectional BFS Util 双向BFS工具类

Utility class for bidirectional BFS search.

双向BFS搜索的工具类。

Features | 特性:

  • Searches from both ends simultaneously | 同时从两端搜索
  • More efficient for large graphs | 对大图更高效
  • O(sqrt(V)) instead of O(V) in best case | 最佳情况下O(sqrt(V))而非O(V)

Usage Examples | 使用示例:

// Find path using bidirectional BFS
List<String> path = BidirectionalBfsUtil.findPath(graph, "A", "Z");

// Check if path exists
boolean exists = BidirectionalBfsUtil.hasPath(graph, "A", "Z");

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty results for null inputs) - 空值安全: 是（null输入返回空结果）

Performance | 性能特性:

  • Time complexity: O(b^(d/2)) where b=branching factor, d=depth - 时间复杂度: O(b^(d/2))，其中b为分支因子，d为深度
  • Space complexity: O(b^(d/2)) - 空间复杂度: O(b^(d/2))
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>
    findPath(Graph<V> graph, V source, V target)
    Find path using bidirectional BFS 使用双向BFS查找路径
    static <V> Set<V>
    findVerticesOnPath(Graph<V> graph, V source, V target, int maxDistance)
    Find all vertices within a certain distance using bidirectional approach 使用双向方法查找特定距离内的所有顶点
    static <V> boolean
    hasPath(Graph<V> graph, V source, V target)
    Check if path exists using bidirectional BFS 使用双向BFS检查路径是否存在
    static <V> int
    shortestPathLength(Graph<V> graph, V source, V target)
    Find shortest path distance using bidirectional BFS (unweighted) 使用双向BFS查找最短路径距离（无权重）

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • findPath

      public static <V> List<V> findPath(Graph<V> graph, V source, V target)
      Find path using bidirectional BFS 使用双向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, or empty list if no path | 路径的顶点列表，无路径时返回空列表

    • hasPath

      public static <V> boolean hasPath(Graph<V> graph, V source, V target)
      Check if path exists using bidirectional BFS 使用双向BFS检查路径是否存在
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      Returns:
      true if path exists | 如果路径存在返回true

    • shortestPathLength

      public static <V> int shortestPathLength(Graph<V> graph, V source, V target)
      Find shortest path distance using bidirectional BFS (unweighted) 使用双向BFS查找最短路径距离（无权重）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      Returns:
      the shortest path length, or -1 if no path | 最短路径长度，无路径时返回-1

    • findVerticesOnPath

      public static <V> Set<V> findVerticesOnPath(Graph<V> graph, V source, V target, int maxDistance)
      Find all vertices within a certain distance using bidirectional approach 使用双向方法查找特定距离内的所有顶点
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      source - the source vertex | 源顶点
      target - the target vertex | 目标顶点
      maxDistance - maximum distance from source | 距源的最大距离
      Returns:
      set of vertices on any shortest path between source and target within distance | 在距离内从源到目标的任何最短路径上的顶点集合