Class GraphUtil

java.lang.Object
com.sure.tool.graph.GraphUtil

public final class GraphUtil extends Object
有向图算法工具:拓扑排序 / 环检测 / DFS / BFS / 可达性 / 无权最短路径。
Since:
1.11.0
  • Method Details

    • topologicalSort

      public static <V> Optional<List<V>> topologicalSort(DiGraph<V> graph)
      Kahn 拓扑排序。
      Type Parameters:
      V - 顶点类型
      Parameters:
      graph - 有向图
      Returns:
      拓扑序;图有环返回 Optional.empty()
    • hasCycle

      public static <V> boolean hasCycle(DiGraph<V> graph)
      环检测(Kahn 计数法:能完成全量拓扑排序则无环)。
      Type Parameters:
      V - 顶点类型
      Parameters:
      graph - 有向图
      Returns:
      true 表示存在环
    • dfs

      public static <V> List<V> dfs(DiGraph<V> graph, V start)
      深度优先遍历(从起点开始,按邻接表顺序)。
      Type Parameters:
      V - 顶点类型
      Parameters:
      graph - 有向图
      start - 起点(不存在时返回空列表)
      Returns:
      访问顺序
    • bfs

      public static <V> List<V> bfs(DiGraph<V> graph, V start)
      广度优先遍历(从起点开始,按邻接表顺序)。
      Type Parameters:
      V - 顶点类型
      Parameters:
      graph - 有向图
      start - 起点(不存在时返回空列表)
      Returns:
      访问顺序
    • isReachable

      public static <V> boolean isReachable(DiGraph<V> graph, V from, V to)
      可达性判断(BFS,源可到目标则 true)。
      Type Parameters:
      V - 顶点类型
      Parameters:
      graph - 有向图
      from - 源顶点
      to - 目标顶点
      Returns:
      true 表示可达(from == to 且存在顶点时视为可达)
    • shortestPath

      public static <V> List<V> shortestPath(DiGraph<V> graph, V from, V to)
      无权图最短路径(BFS),返回路径顶点序列(含起点与终点)。
      Type Parameters:
      V - 顶点类型
      Parameters:
      graph - 有向图
      from - 源顶点
      to - 目标顶点
      Returns:
      最短路径;不可达或顶点缺失返回 null