摘要：图图学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的第5回-《有向图和GabowStrongConnectivityInspector类》，这回学习的主要内容是：
一、强连通有向图
![]()
二、有向图的强连通分量
有向图的极大强连通子图称为的强连通分量，一个非连通的有向图一定会有多个（不少于一个）强连通分量。任何强连通图的强连通分量只有一个，即自身。下面的图5.1中的有向图有3个连通分量。
![]()
第1个强连通分量:([3], [])
第2个强连通分量:([0, 1, 2], [(0,1), (0,2), (1,0), (1,2), (2,0), (2,1)])
第3个强连通分量:([4, 5, 6], [(4,5), (5,6), (6,4)])
三、GabowStrongConnectivityInspector类
GabowStrongConnectivityInspector 类继承自 java.lang.Object，类的实例可用于检查一个有向图是否是强连通图、可用于得到非连通的有向图的全部强连通分量。算法遵循 Gabow（2000 年）在《Path-based depth-first search for strong and biconnected components》中提出的 Cheriyan - Mehlhorn/Gabow 算法。该算法的运行时间复杂度为为 ，其中 是顶点数，是边数。
GabowStrongConnectivityInspector 类的常用方法：
Graph<V,E> getGraph：
返回底层图。
java.util.List<Graph<V,E>> getStronglyConnectedComponents：
返回图的全部强连通分量。
boolean isStronglyConnected：
如果图是强连通的，则返回 true，否则返回 false。
五、代码与效果
将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht，然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录，您可以使用任何自己喜欢的开发目录或名称）。
例子5.1 判断有向图5.1是否是强连通，并的得到强连通分量(效果如图5.2)
如下编译和运行代码。
C:\studyJGrapht>javac -cplib\*;. Ex5_1.javaC:\studyJGrapht>java -cplib\*;. Ex5_1
图5.2 判断有向图是否强连通
Ex5_1.java
importorg.jgrapht.Graph;importorg.jgrapht.graph.DefaultEdge;importorg.jgrapht.graph.SimpleDirectedGraph;importorg.jgrapht.alg.connectivity.GabowStrongConnectivityInspector;importjava.util.Set;importjava.util.List;public classEx5_1{public static void main(String[] args) {// 创建一个有向图，顶点类型为Integer，边类型为 DefaultEdgeGraph<Integer, DefaultEdge> graph = new SimpleDirectedGraph<>(DefaultEdge.class);for(inti=0;i<7;i++) {// 添加顶点graph.addVertex(i);}int[][]a = {{0,1,1,1,0,0,0},{1,0,1,0,0,0,0},{1,1,0,1,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,1,0},{0,0,0,0,0,0,1},{0,0,0,0,1,0,0}};for(inti=0;i<a.length;i++){for(intj=0;j<a[0].length;j++){if(a[i][j]==1) {graph.addEdge(i,j); // 添加边}}}printVertexAndEdge(graph);// 创建 ConnectivityInspector 实例GabowStrongConnectivityInspector<Integer, DefaultEdge> inspector = new GabowStrongConnectivityInspector<>(graph);// 测试图是否强连通System.out.println("图是否强连通: "+ inspector.isStronglyConnected);// 获取图的所有强连通分量List<Graph<Integer, DefaultEdge>> stronglyConnectedComponents =inspector.getStronglyConnectedComponents;System.out.println("所有强连通分量:");inti =1;for(Graph<Integer, DefaultEdge> component : stronglyConnectedComponents) {System.out.println("第"+i+"个强连通分量:"+component);i++;}}private static void printVertexAndEdge(Graph<Integer, DefaultEdge> graph){// 打印图中的所有顶点Set<Integer> allVertex = graph.vertexSet;System.out.println("图中的顶点和边: "+ allVertex+".边：");// 打印图中的所有边Set<DefaultEdge> allEdge = graph.edgeSet;for(DefaultEdge edge : allEdge) {Integer source = graph.getEdgeSource(edge);Integer target = graph.getEdgeTarget(edge);System.out.print(source + "->"+ target+"\t");}System.out.println;}}
![]()
