如何使用 JGraphT 查找指向指定顶点的、固定边数的所有路径-java教程-PHP中文网

如何使用 JGraphT 查找指向指定顶点的、固定边数的所有路径

本文介绍在 jgrapht 中查找所有长度恰好为 k、终点为指定顶点的有向路径的方法，涵盖内置算法的适用限制、方向处理技巧，并提供可落地的动态规划实现方案。

本文介绍在 jgrapht 中查找所有长度恰好为 k、终点为指定顶点的有向路径的方法，涵盖内置算法的适用限制、方向处理技巧，并提供可落地的动态规划实现方案。

JGraphT 本身不提供开箱即用的“所有长度为 k 的入路径”（all incoming paths of length k）功能。其标准最短路径算法（如 DijkstraShortestPath 或 BreadthFirstIterator）默认面向从源点出发的遍历，而用户需求是反向汇聚到目标顶点——即所有以 target 为终点、恰好含 k 条有向边的路径。这要求我们明确处理图的方向性。

⚠️ 内置算法的局限与变通方案

例如，以下代码看似可行，但存在方向陷阱：

DijkstraShortestPath<integer defaultedge> dsp = 
    new DijkstraShortestPath(graph, k); // 注意：k 是最大距离（权重），非边数
SingleSourcePaths<integer defaultedge> paths = dsp.getPaths(targetVertex);</integer></integer>

该调用实际计算的是从 targetVertex 出发、权重 ≤ k 的所有最短路径（即向外辐射），而非指向它的路径。若强行复用，需满足以下任一条件：

将原图转为无向图（丢失方向语义，不推荐）；
反转所有边方向，使原“入边”变为“出边”，再以 targetVertex 为源点运行算法。

但即使如此，DijkstraShortestPath 和 BFS 均只返回每对顶点间的一条最短路径，无法枚举所有可能路径（如 A→B→C 和 A→D→C 同时存在时仅返回其一）。

66AI论文

66AI论文是一款AI论文写作工具，高质量、低查重、低AIGC率的AI论文写作工具。

下载

✅ 推荐方案：反向动态规划（Backward DP）

要精确获取所有长度恰好为 k 的入路径，需自行实现基于反向图的动态规划。核心思想是：

构建原图的反向邻接视图（即对每个顶点 v，获取所有 u 使得 u → v 存在）；
定义 dp[v][i] 为从任意起点出发、经 i 条边到达 v 的所有路径列表；
递推关系：dp[v][i] = ∪{ path + [v] | path ∈ dp[u][i−1], u → v ∈ E }；
初始化：dp[v][0] = [[v]]（长度为 0 的路径仅含自身）。

以下是简洁可运行的实现示例：

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultEdge;
import java.util.*;

public class IncomingPathFinder {
    public static <v e> List<list>> findAllIncomingPathsOfLength(
            Graph<v e> graph, V target, int k) {
        if (k > reverseAdj = new HashMap();
        for (V v : graph.vertexSet()) {
            reverseAdj.put(v, new HashSet());
        }
        for (E edge : graph.edgeSet()) {
            V source = graph.getEdgeSource(edge);
            V targetV = graph.getEdgeTarget(edge);
            reverseAdj.get(targetV).add(source); // u -> v becomes v ← u
        }

        // Step 2: DP table: dp[i] = map of vertex → list of paths ending at vertex with i edges
        List<map list>>>> dp = new ArrayList();
        dp.add(new HashMap()); // k=0
        for (V v : graph.vertexSet()) {
            dp.get(0).put(v, Arrays.asList(Arrays.asList(v)));
        }

        // Step 3: Iterate for length 1 to k
        for (int len = 1; len >> currLevel = new HashMap();
            for (V v : graph.vertexSet()) {
                List<list>> pathsToV = new ArrayList();
                for (V u : reverseAdj.getOrDefault(v, Collections.emptySet())) {
                    List<list>> pathsToU = dp.get(len - 1).getOrDefault(u, Collections.emptyList());
                    for (List<v> path : pathsToU) {
                        List<v> extended = new ArrayList(path);
                        extended.add(v);
                        pathsToV.add(extended);
                    }
                }
                currLevel.put(v, pathsToV);
            }
            dp.add(currLevel);
        }

        return dp.get(k).getOrDefault(target, Collections.emptyList());
    }
}</v></v></list></list></map></v></list></v>

使用示例（对应提问中的图）：

Graph<string defaultedge> g = GraphTypeBuilder.<string defaultedge>directed()
    .allowingMultipleEdges(false).allowingLoops(false).buildGraph();
g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addVertex("D"); g.addVertex("E"); g.addVertex("F");
g.addEdge("A", "B"); g.addEdge("B", "C"); g.addEdge("D", "E"); g.addEdge("E", "C"); g.addEdge("F", "C");

List<list>> result = IncomingPathFinder.findAllIncomingPathsOfLength(g, "C", 2);
// Returns: [["A", "B", "C"], ["D", "E", "C"]]</list></string></string>