JGraphT

Question

下面是遍历图的代码 BreathFirstIterator:

public class GraphTest {

    public static void main(String[] args) {
        DirectedGraph<Integer, DefaultEdge> graph = 
            new DefaultDirectedGraph <Integer, DefaultEdge>(DefaultEdge.class);

        graph.addVertex(7);
        graph.addVertex(4);
        graph.addVertex(9);
        graph.addVertex(3);
        graph.addVertex(2);
        graph.addVertex(5);


        graph.addEdge(7, 4);
        graph.addEdge(7, 9);
        graph.addEdge(9, 3);
        graph.addEdge(3, 2);
        graph.addEdge(3, 5);

        GraphIterator<Integer, DefaultEdge> iterator = 
                new BreadthFirstIterator<Integer, DefaultEdge>(graph);
        while (iterator.hasNext()) {
            System.out.println( iterator.next() );
        }
    }
}

正如预期的那样，代码打印出所有已访问顶点的列表：7,4,9,3,2,5。我的问题是 - 我不知道如何使用此 API 来获取已删除算法回溯的路径。例如，对于从 7 到 2 的路径，它将输出 7->9->3->2，而不仅仅是访问的顶点列表。到达目的地后停止它显然是不够的。有人已经解决了这个问题吗？

Answer 1

使用ClosestFirstIterator可以得到DijkstraShortestPath.findPathBetween. It provides an implementation of Dijkstra's shortest path algorithm两个顶点之间的最短路径。如果没有这个路径，就会return null.

示例代码：

DirectedGraph<Integer, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

graph.addVertex(7);
graph.addVertex(4);
graph.addVertex(9);
graph.addVertex(3);
graph.addVertex(2);
graph.addVertex(5);

graph.addEdge(7, 4);
graph.addEdge(7, 9);
graph.addEdge(9, 3);
graph.addEdge(3, 2);
graph.addEdge(3, 5);

List<DefaultEdge> path = DijkstraShortestPath.findPathBetween(graph, 7, 2);
System.out.println(path); // prints [(7 : 9), (9 : 3), (3 : 2)]

JGraphT - 使用 BreadthFirstIterator 查找路径

JGraphT - Finding path with BreadthFirstIterator

java

graph