Class GraphUtil
java.lang.Object
com.sure.tool.graph.GraphUtil
有向图算法工具:拓扑排序 / 环检测 / DFS / BFS / 可达性 / 无权最短路径。
- Since:
- 1.11.0
-
Method Summary
Modifier and TypeMethodDescriptionstatic <V> List<V> 广度优先遍历(从起点开始,按邻接表顺序)。static <V> List<V> 深度优先遍历(从起点开始,按邻接表顺序)。static <V> boolean环检测(Kahn 计数法:能完成全量拓扑排序则无环)。static <V> booleanisReachable(DiGraph<V> graph, V from, V to) 可达性判断(BFS,源可到目标则 true)。static <V> List<V> shortestPath(DiGraph<V> graph, V from, V to) 无权图最短路径(BFS),返回路径顶点序列(含起点与终点)。topologicalSort(DiGraph<V> graph) Kahn 拓扑排序。
-
Method Details
-
topologicalSort
Kahn 拓扑排序。- Type Parameters:
V- 顶点类型- Parameters:
graph- 有向图- Returns:
- 拓扑序;图有环返回
Optional.empty()
-
hasCycle
环检测(Kahn 计数法:能完成全量拓扑排序则无环)。- Type Parameters:
V- 顶点类型- Parameters:
graph- 有向图- Returns:
- true 表示存在环
-
dfs
-
bfs
-
isReachable
可达性判断(BFS,源可到目标则 true)。- Type Parameters:
V- 顶点类型- Parameters:
graph- 有向图from- 源顶点to- 目标顶点- Returns:
- true 表示可达(from == to 且存在顶点时视为可达)
-
shortestPath
-