jgrapht - 如何确定图中的两个顶点是否相连

Question

SimpleWeightedGraph<String, DefaultWeightedEdge> g = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

    String v1 = "v1";
    String v2 = "v2";
    String v3 = "v3";


    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);


    // add edges to create a path
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);

我使用 JGraphT 库创建一个图形，其中包含从 v1 通过 v2 到 v3 的路径。如何检查 v1 是否连接到 v3？

Answer 1

有很多方法可以做到。我将使用的方法是检查最短路径。只需使用以下 -

DijkstraShortestPath dijk = new DijkstraShortestPath(g, startNode, endNode);
GraphPath<Integer, WeightedEdge> shortestPath = dijk.getPath();

这里 g 是图表。 GraphPath 中的类型与g 中的类型相同。如果存在连接，shortestPath 包含它们之间的最短路径。如果不是，则 shortestPath 等于 null。