本文介绍如何在 jgrapht 中高效获取所有终止于指定顶点、且恰好包含 k 条边的有向路径，涵盖内置算法适配、方向处理技巧及完整自定义动态规划实现。
本文介绍如何在 jgrapht 中高效获取所有终止于指定顶点、且恰好包含 k 条边的有向路径，涵盖内置算法适配、方向处理技巧及完整自定义动态规划实现。
在使用 JGraphT 处理有向图分析时，一个常见但未被直接支持的需求是：枚举所有以某顶点 v 为终点、且长度（边数）恰好为 k 的路径。例如，在图 A→B→C, D→E→C, F→C 中，调用 pathsTo(C, 2) 应返回 [A,B,C] 和 [D,E,C] —— 注意这是 入路径（in-paths），而非从 C 出发的路径。
JGraphT 不提供开箱即用的 allPathsTo(vertex, length) 方法，但可通过以下三种策略实现，需根据场景权衡简洁性与完备性：
✅ 推荐方案：反向图 + BFS 或 Dijkstra（适用于单路径/近似场景）
由于 JGraphT 的最短路径算法（如 DijkstraShortestPath）默认计算从源到目标的路径，要获取“进入 C”的路径，最自然的方式是将图逻辑反转——即构造反向图（C 变为起点），再运行受限深度的遍历：
import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.alg.shortestpath.SingleSourcePaths;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
// 原始有向图
Graph<integer defaultedge> original = new DefaultDirectedGraph(DefaultEdge.class);
original.addVertex(1); original.addVertex(2); original.addVertex(3); // A=1, B=2, C=3
original.addEdge(1, 2); // A→B
original.addEdge(2, 3); // B→C
original.addEdge(4, 5); // D→E
original.addEdge(5, 3); // E→C
original.addEdge(6, 3); // F→C
// 构造反向图（关键步骤）
Graph<integer defaultedge> reversed = Graphs.asUndirected(original); // ❌ 错误！仅当图本就无向才安全
// ✅ 正确做法：显式构建反向有向图
Graph<integer defaultedge> reverseGraph = new DefaultDirectedGraph(DefaultEdge.class);
original.vertexSet().forEach(reverseGraph::addVertex);
original.edgeSet().forEach(e -> reverseGraph.addEdge(
original.getEdgeTarget(e), // 原终点 → 新起点
original.getEdgeSource(e) // 原起点 → 新终点
));
// 从目标顶点 C 开始，找最多 k 条边的路径（Dijkstra 支持权重截断，此处设 unit weight）
DijkstraShortestPath<integer defaultedge> dsp =
new DijkstraShortestPath(reverseGraph, (double) k);
SingleSourcePaths<integer defaultedge> pathsFromC = dsp.getPaths(3); // C=3
// 提取所有距离恰好为 k 的路径（注意：仅返回一条最短路径，非全部）
pathsFromC.getVertexSet().stream()
.filter(v -> pathsFromC.getDistance(v) == k)
.map(pathsFromC::getPath)
.forEach(path -> System.out.println("One path to C of length " + k + ": " + path));</integer></integer></integer></integer></integer>
⚠️ 注意：此方法每顶点仅返回一条路径（最短/最早发现路径），无法覆盖多路径情况（如 A→B→C 和 A→D→C 并存时只返回其一）。若业务允许单解或图中无重路径，该方案简洁高效；否则需转向下述完整方案。
⚙️ 完整方案：动态规划枚举所有 k-边入路径（推荐用于精确需求）
为确保获取 所有 长度为 k 的入路径，需手动实现基于状态 (vertex, length) 的记忆化搜索。核心思想是：
pathsTo(v, k) = 所有 u 满足 u → v ∈ E 的 pathsTo(u, k−1) 后缀拼接 v
以下是可直接运行的通用实现：
import java.util.*;
public class AllPathEnumerator {
private final Graph<integer defaultedge> graph;
public AllPathEnumerator(Graph<integer defaultedge> graph) {
this.graph = graph;
}
/**
* 返回所有以 target 终止、且恰好含 k 条边的路径（每个路径为顶点列表，从起点到 target）
*/
public List<list>> allPathsTo(Integer target, int k) {
if (k >>> memo = new HashMap();
return dfs(target, k, memo);
}
private List<list>> dfs(Integer v, int len,
Map<integer map list>>>> memo) {
if (len == 0) {
return Collections.singletonList(Collections.singletonList(v));
}
if (len == 1) {
List<list>> result = new ArrayList();
for (Integer u : Graphs.predecessorListOf(graph, v)) {
result.add(Arrays.asList(u, v));
}
return result;
}
memo.computeIfAbsent(v, k -> new HashMap());
if (memo.get(v).containsKey(len)) {
return memo.get(v).get(len);
}
List<list>> result = new ArrayList();
for (Integer u : Graphs.predecessorListOf(graph, v)) {
List<list>> prevPaths = dfs(u, len - 1, memo);
for (List<integer> path : prevPaths) {
List<integer> extended = new ArrayList(path);
extended.add(v);
result.add(extended);
}
}
memo.get(v).put(len, result);
return result;
}
}
// 使用示例
AllPathEnumerator enumerator = new AllPathEnumerator(original);
List<list>> paths = enumerator.allPathsTo(3, 2); // C=3, k=2
paths.forEach(System.out::println); // 输出: [1, 2, 3], [4, 5, 3]</list></integer></integer></list></list></list></integer></list></list></integer></integer>
✅ 优势：精确、完备、支持任意 k、自动去重（路径本身不同即视为不同）、时间复杂度可控（O(|E| × k × avg_path_count)）。
? 优化提示：对大规模图，可增加 maxResults 限制或改用迭代 DP 表避免递归栈溢出。
? 总结与选型建议
- 若只需一条代表路径且图稀疏 → 使用 反向图 + DijkstraShortestPath 或 BreadthFirstIterator（设置 maxDepth = k）；
- 若需全部路径且 k 较小（≤ 10）→ 采用上述 DFS+记忆化动态规划，代码清晰、易于调试；
- 避免 Floyd-Warshall：其时间复杂度 O(|V|³) 过高，且仍需额外回溯生成路径，得不偿失；
- 始终验证图方向：JGraphT 的 predecessorListOf(graph, v) 是获取入边邻居的正确方式，无需手动反转图结构。
通过合理选择策略，你能在 JGraphT 生态中稳健实现“指定长度入路径枚举”这一关键图分析能力。
