JGraphT技术咨询：如何获取指定顶点的指定长度入路径

问题描述 #

我正在使用JGraphT库，需要实现一个功能：计算**终止于指定顶点、长度为特定值（边的数量）**的所有入路径。

举个例子，给定有向图：

• A -> B
• B -> C
• D -> E
• E -> C
• F -> C

需要一个类似function(node, k)的方法，调用function(C, 2)时，返回所有包含2条边且终止于C的路径：(A, B, C), (D, E, C)。

已查阅JGraphT的API文档，只找到两点间路径的相关函数，未找到获取某顶点所有入路径的对应功能，想知道该功能是否为JGraphT原生支持，还是需要自行实现算法。

回答 #

JGraphT库没有原生提供这个特定功能，需要自行编写算法实现。

实现思路 #

推荐使用动态规划的方式实现（效率更高，适配无环/有环图场景）：

• 维护动态规划表dp，其中dp[i][v]表示长度为i（包含i条边）、终止于顶点v的所有路径集合。
• 初始化：dp[0][v]为只包含顶点v自身的路径（长度为0，无关联边）。
• 递推过程：遍历每个长度i（从1到k），对图中所有边u->v，将dp[i-1][u]中的每条路径末尾添加v，存入dp[i][v]的路径集合。

代码示例 #

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

public class TargetPathFinder {
    // 找到终止于target、长度为k（k条边）的所有路径
    public static <V, E> List<List<V>> findPathsOfLengthK(Graph<V, E> graph, V target, int k) {
        if (k < 0) return Collections.emptyList();
        
        // dp[i]：键为顶点，值为该顶点的长度i路径列表
        Map<Integer, Map<V, List<List<V>>>> dp = new HashMap<>();
        
        // 初始化长度0的路径：每个顶点自己
        Map<V, List<List<V>>> zeroLengthPaths = new HashMap<>();
        for (V vertex : graph.vertexSet()) {
            List<List<V>>> paths = new ArrayList<>();
            List<V> singleNodePath = new ArrayList<>();
            singleNodePath.add(vertex);
            paths.add(singleNodePath);
            zeroLengthPaths.put(vertex, paths);
        }
        dp.put(0, zeroLengthPaths);
        
        // 递推计算长度1到k的路径
        for (int i = 1; i <= k; i++) {
            Map<V, List<List<V>>> currentLevel = new HashMap<>();
            for (E edge : graph.edgeSet()) {
                V source = graph.getEdgeSource(edge);
                V dest = graph.getEdgeTarget(edge);
                
                // 获取长度i-1的、终止于source的路径
                List<List<V>>> prevPaths = dp.get(i-1).getOrDefault(source, Collections.emptyList());
                for (List<V> prevPath : prevPaths) {
                    // 复制路径并添加当前目标节点
                    List<V> newPath = new ArrayList<>(prevPath);
                    newPath.add(dest);
                    // 加入当前层级的对应节点路径集合
                    currentLevel.computeIfAbsent(dest, key -> new ArrayList<>()).add(newPath);
                }
            }
            dp.put(i, currentLevel);
        }
        
        return dp.get(k).getOrDefault(target, Collections.emptyList());
    }

    public static void main(String[] args) {
        // 构建示例图
        Graph<String, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);
        String[] vertices = {"A", "B", "C", "D", "E", "F"};
        for (String v : vertices) graph.addVertex(v);
        graph.addEdge("A", "B");
        graph.addEdge("B", "C");
        graph.addEdge("D", "E");
        graph.addEdge("E", "C");
        graph.addEdge("F", "C");
        
        // 测试调用：找终止于C、长度为2的路径
        List<List<String>> resultPaths = findPathsOfLengthK(graph, "C", 2);
        for (List<String> path : resultPaths) {
            System.out.println(path);
        }
        // 输出结果：[A, B, C]、[D, E, C]
    }
}

内容的提问来源于stack exchange，提问作者Austin Mordahl