使用JGraphT获取简单无向图两节点间所有路径的方法咨询

问题原因 #

JGraphT的AllDirectedPaths工具类仅支持有向图结构，传入无向图实例时会触发类型校验异常，无法直接复用。

可行解决方案 #

方案1：直接使用通用的AllSimplePaths工具类（推荐）

JGraphT提供了适配所有图类型（含无向图、有向图）的AllSimplePaths类，专门用于枚举两个节点之间的所有简单路径（路径中节点不重复），直接适配无向图场景，示例代码如下：

import org.jgrapht.GraphPath;
import org.jgrapht.alg.shortestpath.AllSimplePaths;
import java.util.List;

// 你的无向图实例，节点类型Country，边类型DefaultEdge
Graph<Country, DefaultEdge> undirectedGraph = ...; 
AllSimplePaths<Country, DefaultEdge> pathFinder = new AllSimplePaths<>(undirectedGraph);

// 枚举起点countries.get(220)到终点countries.get(325)的所有简单路径
// 第四个参数为路径最大长度限制，传null表示无限制
List<GraphPath<Country, DefaultEdge>> allPaths = pathFinder.getAllPaths(
    countries.get(220), 
    countries.get(325), 
    true, 
    null
);

// 遍历找最长路径
GraphPath<Country, DefaultEdge> longestPath = null;
int maxLength = -1;
for (GraphPath<Country, DefaultEdge> path : allPaths) {
    if (path.getLength() > maxLength) {
        maxLength = path.getLength();
        longestPath = path;
    }
}
return longestPath;

方案2：将无向图转换为等价有向图复用原有逻辑

如果要复用你已有的AllDirectedPaths代码，可以将无向图的每条边拆为两条方向相反的有向边，构造对应的有向图实例后再调用原有方法即可，注意调用getAllPaths时要开启简单路径校验（第三个参数设为true），避免出现同一条边往返走的无效路径。

注意事项 #

两点之间的最长路径问题属于NP难问题，上述枚举全路径的方案仅适合节点规模小于20的小图使用；如果你的图节点数较多，需要改用近似算法（如随机游走、启发式搜索等）获取近似最长路径。

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