在计算机科学中，有向图是一种重要的数据结构，由顶点和有方向边组成，常用于表示依赖关系、网络拓扑、任务调度等场景，Java作为主流编程语言，提供了多种方式实现有向图，本文将详细介绍基于邻接矩阵、邻接表以及第三方库的实现方法,并探讨实际应用中的注意事项。
基于邻接矩阵的实现
邻接矩阵用二维数组表示顶点间的连接关系，适合顶点数量较少的稠密图，矩阵中matrix[i][j]的值表示顶点i到顶点j的边（有权重时存权重，无权重时存0或1）。
实现步骤：
- 定义图类，初始化顶点数组和邻接矩阵；
- 添加顶点（若顶点已存在则跳过）；
- 添加有向边，设置矩阵对应位置的值；
- 可扩展删除边、打印矩阵等方法。
代码示例：
public class AdjacencyMatrixGraph {
private int vertices; // 顶点数
private int[][] matrix; // 邻接矩阵
public AdjacencyMatrixGraph(int vertices) {
this.vertices = vertices;
matrix = new int[vertices][vertices];
}
public void addEdge(int src, int dest) {
matrix[src][dest] = 1; // 有向边：src→dest
}
public void printMatrix() {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
优缺点：查找边的时间复杂度为O(1)，但空间复杂度为O(V²)，顶点多时浪费内存,适合稠密图。
基于邻接表的实现
邻接表用链表或动态数组存储每个顶点的邻接点，适合稀疏图，空间效率更高，Java中可通过List<List<Integer>>或自定义节点类实现。
实现步骤：
- 使用
List<List<Integer>>存储邻接表，索引对应顶点； - 添加顶点时初始化对应位置的链表；
- 添加有向边时，在源顶点链表中添加目标顶点。
代码示例：
import java.util.ArrayList;
import java.util.List;
public class AdjacencyListGraph {
private int vertices;
private List<List<Integer>> adjList;
public AdjacencyListGraph(int vertices) {
this.vertices = vertices;
adjList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int src, int dest) {
adjList.get(src).add(dest); // 有向边：src→dest
}
public void printList() {
for (int i = 0; i < vertices; i++) {
System.out.print("顶点 " + i + ": ");
for (int neighbor : adjList.get(i)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}
}
优缺点：空间复杂度为O(V+E)，添加边的时间复杂度为O(1)，但查找边需遍历链表,适合稀疏图。
使用JGraphT第三方库
对于复杂图操作（如遍历、最短路径等），可借助第三方库JGraphT，它提供了丰富的图算法接口。
实现步骤：
- 添加依赖（Maven）：
<dependency> <groupId>org.jgrapht</groupId> <artifactId>jgrapht-core</artifactId> <version>1.5.0</version> </dependency> - 创建有向图实例（如
DefaultDirectedGraph）； - 添加顶点和边，使用
addVertex()和addEdge()。
代码示例：
import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
public class JGraphTExample {
public static void main(String[] args) {
// 创建有向图，边使用DefaultEdge
Graph<String, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);
// 添加顶点
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
// 添加有向边
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("A", "C");
// 打印边
System.out.println("图的边：");
for (DefaultEdge edge : graph.edgeSet()) {
System.out.println(graph.getEdgeSource(edge) + " → " + graph.getEdgeTarget(edge));
}
}
}
优点：支持多种图类型（有向/无向、带权/无权），内置DFS、BFS、Dijkstra等算法,适合复杂场景。
实际应用场景
有向图在Java中广泛应用于多个领域：
- 社交网络：用户关注关系（A关注B，边为A→B）；
- 任务调度：任务依赖关系（任务A依赖任务B，边为B→A）；
- 网络路由：数据包传输路径（路由器间的方向边）；
- 编译原理：语法分析树中的依赖关系。
注意事项
- 数据结构选择：根据图的稀疏性选择邻接矩阵（稠密图）或邻接表（稀疏图）；
- 顶点与边的标识：可使用字符串、对象等作为顶点标识，避免仅用整数索引；
- 第三方库版本：使用JGraphT时注意版本兼容性，避免API变更；
- 性能优化：大规模图需考虑内存占用，可结合堆优化或分片存储。
通过以上方法，Java开发者可根据需求灵活实现有向图，基础方法适合学习数据结构原理，第三方库则能高效解决工程问题,合理选择可提升开发效率与代码质量。
