本文介绍在 jgrapht 中查找所有长度恰好为 k、终点为给定顶点的有向路径的多种方法，涵盖内置算法的巧妙适配与自定义动态规划实现，并重点说明方向性处理与多路径枚举的关键细节。
本文介绍在 jgrapht 中查找所有长度恰好为 k、终点为给定顶点的有向路径的多种方法，涵盖内置算法的巧妙适配与自定义动态规划实现，并重点说明方向性处理与多路径枚举的关键细节。
JGraphT 并未直接提供“所有长度为 k 的入路径（in-paths）”的开箱即用方法（如 getAllInPathsOfLength(target, k)），但可通过合理组合现有工具或编写轻量级递归/动态规划逻辑高效实现。核心挑战在于：路径需严格满足边数 = k，且终点固定；在有向图中，必须逆向遍历（即沿反向边搜索）才能自然建模“流入”语义。
✅ 推荐方案：基于反向图的 BFS 或 DFS 枚举（准确、完整、可控）
最可靠的方式是构建原图的反向图（reversed graph），然后从目标顶点出发执行受限深度的遍历。JGraphT 提供 Graphs.reverse() 工具方法，可零成本生成逻辑反向视图：
import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.Graphs;
import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.traverse.DepthFirstIterator;
// 假设原始有向图 graph 已构建（如 A→B, B→C, D→E, E→C, F→C）
Graph<String, DefaultEdge> originalGraph = new DefaultDirectedGraph<>(DefaultEdge.class);
// ... 添加顶点和边
// 步骤1：创建反向图（自动将所有边方向翻转）
Graph<String, DefaultEdge> reversedGraph = Graphs.reverse(originalGraph);
// 步骤2：从目标顶点 C 开始 BFS，限制最大深度为 k
String target = "C";
int k = 2;
List<List<String>> allPaths = new ArrayList<>();
Deque<List<String>> queue = new ArrayDeque<>();
// 初始化：路径仅含目标顶点
queue.offer(Arrays.asList(target));
while (!queue.isEmpty() && !queue.peek().isEmpty()) {
List<String> currentPath = queue.poll();
int depth = currentPath.size() - 1; // 路径边数 = 顶点数 - 1
if (depth == k) {
Collections.reverse(currentPath); // 还原为正向路径（起点→终点）
allPaths.add(currentPath);
continue;
}
// 获取当前路径末端顶点的所有前驱（即反向图中的邻居）
String last = currentPath.get(currentPath.size() - 1);
for (String predecessor : reversedGraph.vertexSet()) {
if (reversedGraph.containsEdge(predecessor, last)) {
List<String> newPath = new ArrayList<>(currentPath);
newPath.add(predecessor);
queue.offer(newPath);
}
}
}
// 输出结果：[(A, B, C), (D, E, C)]
System.out.println(allPaths);⚠️ 注意事项：
- 此方法保证枚举所有长度恰好为 k 的入路径（包括多条平行路径，如 A→B→C 和 A→D→C）；
- 时间复杂度取决于图规模与 k 值，对稀疏图和中等 k 值（≤10）高效；
- 若需避免重复路径（如存在环），应在遍历中加入已访问顶点集合剪枝。
⚠️ 替代方案辨析（适用场景有限）
DijkstraShortestPath + radius 限制：
如答案所述，DijkstraShortestPath(graph, radius) 可限制搜索范围，但其本质是单源最短路径，仅返回每个顶点到源的一条最短路径。即使设置 radius = k，也无法获取所有长度为 k 的路径（尤其当存在多条等长路径时），且默认方向与需求相反——必须配合反向图使用，否则结果无意义。Floyd-Warshall + 路径重建：
适用于需要多次查询不同 k 值的场景，但空间复杂度 O(V²)、时间 O(V³)，且路径重建逻辑复杂，不推荐用于单次 k 查询。正向 BFS / DFS 从所有顶点出发：
效率低下（O(V × (V+E))），需对每个顶点运行一次受限遍历，远不如反向图单源遍历简洁。
✅ 总结建议
| 需求 | 推荐方法 |
|---|---|
| 精确获取所有长度为 k 的入路径（含多路径） | ✅ 构建反向图 + DFS/BFS 枚举（代码示例见上） |
| 仅需一条最短入路径，且 k 即最短距离 | ⚠️ DijkstraShortestPath（反向图上运行） |
| k 值极小（如 1~3）、图极大、内存敏感 | ✅ 手写迭代式邻接表回溯（避免递归栈开销） |
最终，反向图 + 受限遍历是最通用、最易理解、最符合问题语义的解决方案。它直击本质：将“所有进入 C 的长度为 2 的路径”转化为“从 C 出发，在反向图中走 2 步能到达的所有起点路径”，逻辑清晰，代码健壮，且完全兼容 JGraphT 的设计哲学。
