如何使用JGraphT裁剪出距指定节点距离不超过K的子图

• 你当前使用的全节点对最短路径方案存在大量冗余计算，你仅需要源节点N到其他节点的距离数据，完全不需要全局节点对的计算结果，优化后效率至少可以提升数倍。
• 无权重有向图场景，直接使用限定深度的BFS遍历：从源节点N出发逐层遍历，遍历深度不超过K时停止，遍历过程中接触到的所有节点就是符合距离要求的节点，时间复杂度仅和符合要求的节点、边数量正相关，不需要处理全图无关节点。
• 带权重有向图场景，使用距离截断的Dijkstra算法：从源节点N出发计算最短路径，当优先队列弹出的节点最短距离已经超过K时，直接终止算法，不需要处理剩余更远的节点。
• 收集到符合要求的节点后，直接基于原图生成子视图即可，不需要额外复制图结构。

JGraphT没有单独封装「K距离子图提取」的独立接口，但是可以通过原生提供的迭代器/最短路径工具 + 子图工具组合实现，不需要自己手动实现遍历逻辑：

无权重图实现示例 #

import org.jgrapht.Graph;
import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.graph.AsSubgraph;
import java.util.HashSet;
import java.util.Set;

// 泛型替换为你实际的节点、边类型
public <V, E> AsSubgraph<V, E> extractKDistanceSubgraph(Graph<V, E> originGraph, V sourceNode, int maxDistance) {
    // 初始化带最大深度限制的BFS迭代器
    BreadthFirstIterator<V, E> bfsIterator = new BreadthFirstIterator<>(originGraph, sourceNode, maxDistance);
    // 收集所有符合距离要求的节点
    Set<V> validNodes = new HashSet<>();
    bfsIterator.forEachRemaining(validNodes::add);
    // 生成子图，自动保留合法节点之间的原有边
    return new AsSubgraph<>(originGraph, validNodes);
}

带权重图实现示例 #

import org.jgrapht.Graph;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.AsSubgraph;
import java.util.Set;

// 泛型替换为你实际的节点、边类型
public <V, E> AsSubgraph<V, E> extractKWeightDistanceSubgraph(Graph<V, E> originGraph, V sourceNode, double maxWeightDistance) {
    // 初始化带最大距离截断的Dijkstra算法
    DijkstraShortestPath<V, E> dijkstra = new DijkstraShortestPath<>(originGraph, maxWeightDistance);
    // 获取所有距离不超过K的节点集合
    Set<V> validNodes = dijkstra.getPaths(sourceNode).getPaths().keySet();
    // 生成子图
    return new AsSubgraph<>(originGraph, validNodes);
}

提示：如果你的图是有权重的负权图，将上述DijkstraShortestPath替换为BellmanFordShortestPath即可，同样支持传入最大距离参数做截断。上述代码返回的AsSubgraph是原图的视图，修改原图会同步影响子图内容，如果需要独立的子图实例，初始化新的图对象将子图的节点、边批量添加即可。

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