Class GraphTraversalUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.GraphTraversalUtil
public final class GraphTraversalUtil extends Object
Graph Traversal Util 图遍历工具类

Utility class for graph traversal algorithms (BFS/DFS).

图遍历算法（BFS/DFS）的工具类。

Algorithms | 算法:

  • BFS - Breadth-First Search | 广度优先搜索
  • DFS - Depth-First Search | 深度优先搜索

Time Complexity | 时间复杂度: O(V + E)

Space Complexity | 空间复杂度: O(V)

Features | 主要功能:

  • Breadth-first search (BFS) traversal - 广度优先搜索遍历
  • Depth-first search (DFS) traversal - 深度优先搜索遍历
  • Visitor callback support - 访问者回调支持
  • Configurable max depth to prevent stack overflow - 可配置最大深度防止栈溢出

Usage Examples | 使用示例:

List<String> bfsResult = GraphTraversalUtil.bfs(graph, "A");
List<String> dfsResult = GraphTraversalUtil.dfs(graph, "A");

// With visitor
GraphTraversalUtil.bfs(graph, "A", vertex -> System.out.println(vertex));

Security | 安全性:

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

Performance | 性能特性:

  • Time complexity: O(V + E) - 时间复杂度: O(V + E)
  • Space complexity: O(V) - 空间复杂度: O(V)
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>
    bfs(Graph<V> graph, V start)
    Breadth-First Search 广度优先搜索
    static <V> void
    bfs(Graph<V> graph, V start, Consumer<V> visitor)
    Breadth-First Search with visitor 带访问器的广度优先搜索
    static <V> List<V>
    bfsAll(Graph<V> graph)
    Traverse all vertices (handles disconnected components) 遍历所有顶点（处理不连通分量）
    static <V> List<V>
    dfs(Graph<V> graph, V start)
    Depth-First Search (iterative) 深度优先搜索（迭代）
    static <V> void
    dfs(Graph<V> graph, V start, Consumer<V> visitor)
    Depth-First Search with visitor (iterative) 带访问器的深度优先搜索（迭代）
    static <V> List<V>
    dfsAll(Graph<V> graph)
    Traverse all vertices using DFS (handles disconnected components) 使用DFS遍历所有顶点（处理不连通分量）

    Methods inherited from class Object

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

  • Method Details

    • 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 | 图
      start - the starting vertex | 起始顶点
      Returns:
      list of vertices in BFS order | BFS顺序的顶点列表

    • bfs

      public static <V> void bfs(Graph<V> graph, V start, Consumer<V> visitor)
      Breadth-First Search with visitor 带访问器的广度优先搜索
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      start - the starting vertex | 起始顶点
      visitor - the vertex visitor | 顶点访问器

    • dfs

      public static <V> List<V> dfs(Graph<V> graph, V start)
      Depth-First Search (iterative) 深度优先搜索（迭代）

      Uses an explicit stack instead of recursion to avoid StackOverflowError on deep graphs.

      使用显式栈代替递归，避免深层图上的 StackOverflowError。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      start - the starting vertex | 起始顶点
      Returns:
      list of vertices in DFS order | DFS顺序的顶点列表

    • dfs

      public static <V> void dfs(Graph<V> graph, V start, Consumer<V> visitor)
      Depth-First Search with visitor (iterative) 带访问器的深度优先搜索（迭代）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      start - the starting vertex | 起始顶点
      visitor - the vertex visitor | 顶点访问器

    • bfsAll

      public static <V> List<V> bfsAll(Graph<V> graph)
      Traverse all vertices (handles disconnected components) 遍历所有顶点（处理不连通分量）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      list of all vertices in BFS order | BFS顺序的所有顶点列表

    • dfsAll

      public static <V> List<V> dfsAll(Graph<V> graph)
      Traverse all vertices using DFS (handles disconnected components) 使用DFS遍历所有顶点（处理不连通分量）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      list of all vertices in DFS order | DFS顺序的所有顶点列表