耿老师教你学Java:图图学JGraphT开源框架第14回
创始人
2025-03-12 08:40:06
0

摘要:图图学JGraphT开源框架是教材《数据结构与算法》-java语言版(清华大学出版社-2024,耿祥义,张跃平)第13章《图论》的课外读物(共计19回),所以主要围绕教材的内容学习JGraphT开源框架,即学JGraphT开源框架最重要的部分,不是学习JGraphT开源框架的全部内容(JGraphT开源框架封装关于最短路径的算法类就有30多个)。掌握这里的这些内容,也可以让我们在实际项目更加容易地使用图论的算法,这也正是框架的目的。

图图学开源JGraphT开源框架目录如下

第1回《无向图和SimpleGraph 类》 第2回《Graph 接口》 第3回《无向图和BiconnectivityInspector 类》 第4回《有向图和SimpleDirectedGraph类》 第5回《有向图和GabowStrongConnectivityInspector类》 第6回《有向图与AllDirectedPaths类》 第7回《无向网络和SimpleWeightedGraph 类》 第8回《有向网络和SimpleDirectedWeightedGraph类》 第9回《深度优先搜索(DFS)和DepthFirstIterator类》 第10回《广度优先搜索(BFS)和BreadthFirstIterator类》 第11回《最短路径和FloydWarshallShortestPaths类》 第12回《最短路径和DijkstraShortestPath类》 第13回《最短路径和BFSShortestPath类》 第14回《第k短路径和EppsteinKShortestPath类》 第15回《最小生成树和PrimMinimumSpanningTree类》 第16回《拓扑排序和TopologicalOrderIterator类》 第17回《图着色与GreedyColoring类》 第18回《介数和Betweenness Centrality类》 第19回《最大流算法和EdmondsKarpMFImpl类》

这是

图图学开源JGraphT的第14回-《第k短路径和EppsteinKShortestPath类》,这回学习的主要内容是:

  • 最短路径

  • EppsteinKShortestPath类

  • 一、最短路径

GraphPath接口

实现GraphPath接口的对象用于存储路径,也见第6回(包括非简单路径),接口的方法如下:

defaultjava.util.List getEdgeList:返回构成路径的全部边。 V getEndVertex:返回路径中的终点顶点。 defaultintgetLength:返回路径的长度,以边的数量来衡量。 V getStartVertex:返回路径中的起点顶点。 defaultjava.util.List getVertexList:将路径中的顶点序列。 doublegetWeight:返回分配给该路径的权重(路径中边的权重之和)。

二、EppsteinKShortestPath类

JGaphT框架称:大卫・埃普斯坦(David Eppstein)在1999 年给出寻找第 k 短的路径发表在《工业与应用数学学会计算期刊》(SIAM J. Comput.)第 28 卷,第 2 期(1999 年 2 月)第 652 - 673 页。该算法的主要优点在于它能达到 O(m+nlogn+klogk)的时间复杂度,同时保证所生成的k条路径按权重升序排列。其中,m是图中边的数量,n是图中顶点的数量,k是所需路径的数量。此实现仅适用于有向网络简单图

// 创建 EppsteinKShortestPath 实例 EppsteinKShortestPath eppstein = new EppsteinKShortestPath<>(graph); // 获取 k 条最短路径 List> paths = eppstein.getPaths(source, target, k);

三、代码与效果

将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht,然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录,您可以使用任何自己喜欢的开发目录或名称)。

例子14.1 第k短的路径(效果如图14.1)

求下列有向网络的顶点到顶点的第k短路径。

如下编译运行代码。

C:\studyJGrapht>javac -cplib\*;. Ex14_1.java C:\studyJGrapht>java -cplib\*;. Ex14_1

图14.1 第k短路径

Ex14_1.java

importorg.jgrapht.Graph; importorg.jgrapht.GraphPath; importorg.jgrapht.alg.shortestpath.EppsteinKShortestPath; importorg.jgrapht.graph.DefaultWeightedEdge; importorg.jgrapht.graph.SimpleDirectedWeightedGraph; importjava.util.List; public classEx14_1{ public static void main(String[] args) { // 创建一个有向加权简单图 Graph graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class); // 添加顶点 graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D");

// 添加边并设置权重graph.setEdgeWeight(graph.addEdge("A", "B"), 1);graph.setEdgeWeight(graph.addEdge("B", "C"), 2);graph.setEdgeWeight(graph.addEdge("C", "D"), 3);graph.setEdgeWeight(graph.addEdge("A", "D"), 7);graph.setEdgeWeight(graph.addEdge("A", "C"), 5);// 定义起点、终点和要查找的最短路径数量String source = "A";String target = "D";intk = 3;// 创建 EppsteinKShortestPath 实例EppsteinKShortestPath eppstein = new EppsteinKShortestPath<>(graph);// 获取 k 条最短路径List> paths = eppstein.getPaths(source, target, k);// 输出结果System.out.println( source + " 到 "+ target );if(paths != null) {for(inti = 0; i < paths.size; i++) {GraphPath path = paths.get(i);System.out.println("第 "+ (i + 1) + " 条最短路径: "+ path.getVertexList);System.out.print(path.getEdgeList);//JGraphT的默认格式里是冒号System.out.println("路径权重: "+ path.getWeight);printPath(path);}} else{System.out.println("未找到从 "+ source + " 到 "+ target + " 的路径。");}}// 打印最短路径及其权重的方法public static void printPath(GraphPath shortestPath) {List vertexList = shortestPath.getVertexList;StringBuilder pathStr = new StringBuilder;for(inti = 0; i < vertexList.size; i++) {pathStr.append(vertexList.get(i));if(i < vertexList.size - 1) {pathStr.append(" -> ");}}System.out.println(pathStr + "(路径权重:"+ shortestPath.getWeight+")");}}

相关内容

热门资讯

加强新能源汽车停放充电区管理 转自:团结报  近年来,我国新能源汽车产业发展迅猛,新能源汽车保有量已突破3000万辆大关,成为全球...
中国队提前小组出线   本报讯(记者 卓然)北京时间昨日,在塞尔维亚举行的2025年世界U19女排锦标赛中,中国队1比3...
从“难言之隐”到“声控无忧” 转自:团结报  □ 本报通讯员 王  茜 刘高峰 记者 邱  凌  不久前,在中共吉林省委社会工作部...
共绘雪域高原同心圆   “坚持全国一盘棋,相互帮助,特别是沿海地区要帮助西部地区,发达地区要帮助欠发达地区,都要找准角色...
和田北京路上的援疆见证   本报特派记者 曹政  新疆和田,一条北京路横贯东西。与北京结缘的不只是名字,路两侧的众多地标也是...