耿老师教你学Java：图图学JGraphT开源框架第18回_科学探索

耿老师教你学Java：图图学JGraphT开源框架第18回

创始人

2025-03-16 10:12:16

摘要：图图学JGraphT开源框架是教材《数据结构与算法》-java语言版（清华大学出版社-2024，耿祥义，张跃平）第13章《图论》的课外读物（共计19回25个实例），所以主要围绕教材的内容学习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的第18回-《介数和Betweenness Centrality类》，这回学习的主要内容是：

介数
Betweenness Centrality类

一、介数

一个顶点的介数是该顶点在其他所有顶点对之间最短路径上出现的频率。如果一个顶点的介数很高，说明它在图的连通性中起到重要的桥梁作用。以下是JGraphT的解释：

Computes the betweenness centrality of each vertex of a graph. The betweenness centrality of a node v

vis given by the expression: g

(v)=∑

s≠v≠t

(v)

g(v)=∑s≠v≠tσst(v)σstwhere σ

σstis the total number of shortest paths from node s

sto node t

tand σ

(v)

σst(v)is the number of those paths that pass through v

v. F

二、Betweenness Centrality类

BetweennessCentrality的实例可给出每个顶点vertex的介数。

BetweennessCentrality<String, DefaultEdge> betweennessCentrality = newBetweennessCentrality<>(graph); double count =betweennessCentrality.getVertexScore(vertex)；；

三、代码与效果

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

例子18.1 顶点的介数（效果如图18.1)

如下编译和运行代码。

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

图18.1 顶点的介数

Ex18_1.java

importorg.jgrapht.Graph; importorg.jgrapht.alg.scoring.BetweennessCentrality; importorg.jgrapht.graph.DefaultEdge; importorg.jgrapht.graph.SimpleGraph; importjava.util.*; public classEx18_1{ public static void main(String[] args) { // 创建一个简单无向图 Graph graph = new SimpleGraph<>(DefaultEdge.class); String prince[] = {"山东","河南","江苏","安徽","湖南","江西","浙江","福建","广东","湖北"}; // 添加顶点 for(String vertex:prince){ graph.addVertex(vertex); } graph.addEdge("山东","河南"); graph.addEdge("山东","江苏"); graph.addEdge("山东","安徽"); graph.addEdge("河南","湖北"); graph.addEdge("河南","安徽"); graph.addEdge("江苏","安徽"); graph.addEdge("浙江","安徽"); graph.addEdge("江苏","浙江"); graph.addEdge("湖北","安徽"); graph.addEdge("湖北","江西"); graph.addEdge("湖北","湖南"); graph.addEdge("湖北","河南"); graph.addEdge("江西","湖南"); graph.addEdge("广东","湖南"); graph.addEdge("江西","安徽"); graph.addEdge("江西","广东"); graph.addEdge("江西","福建"); graph.addEdge("江西","浙江"); graph.addEdge("浙江","江苏"); graph.addEdge("浙江","福建"); graph.addEdge("广东","福建"); // 创建 BetweennessCentrality 实例 BetweennessCentrality betweennessCentrality = new BetweennessCentrality<>(graph); for(String vertex:graph.vertexSet){ String s= String.format("%.2f",betweennessCentrality.getVertexScore(vertex)); System.out.println("顶点 "+ vertex + " 的介数: "+s); } System.out.println("使用另外一个方法再输出一次:"); Map centralityMap = betweennessCentrality.getScores; for(Map.Entry entry : centralityMap.entrySet) { String vertex = entry.getKey; String s= String.format("%.2f",entry.getValue); System.out.println("顶点 "+ vertex + " 的介数: "+ s); } System.out.println("按介数排序:"); graph.vertexSet.stream .sorted((a,b)->(int)(betweennessCentrality.getVertexScore(a)*1000)-(int)(betweennessCentrality.getVertexScore(b)*1000)) .forEach(v->System.out.print(" "+v+":"+String.format("%.2f",betweennessCentrality.getVertexScore(v)))); }}

the Java 算法顶点 vertex 路径 JGraphT 目录图图框架介数江西安徽

⚠️

本网站信息内容及素材来源于网络采集或用户发布，如涉及侵权，请及时联系我们，发送链接至2697952338@QQ.COM，我们将第一时间进行核实与删除处理。

上一篇：macOS频繁报错处理指南：有效解决系统错误提示问题

下一篇：跟着AI买彩票，一场“注资返现”骗局

耿老师教你学Java：图图学JGraphT开源框架第18回

相关内容

热门资讯