深入理解Java有向图（从零开始掌握Java有向图实现与图算法）

如何在Java中表示有向图？

常见的表示方法有两种：

• 邻接矩阵（Adjacency Matrix）：使用二维数组，适合稠密图。
• 邻接表（Adjacency List）：使用链表或列表的数组，适合稀疏图，更节省空间。

本教程采用邻接表方式，因为它在大多数实际应用中效率更高，也是学习Java有向图实现的最佳起点。

步骤一：定义图的顶点

我们可以用整数或字符串表示顶点。为简化，这里使用整数作为顶点编号。

步骤二：使用Java实现有向图类

下面是一个完整的、易于理解的有向图邻接表Java实现：

import java.util.*;public class DirectedGraph {    // 使用HashMap存储每个顶点及其邻接顶点列表    private Map<Integer, List<Integer>> adjList;    public DirectedGraph() {        adjList = new HashMap<>();    }    // 添加顶点    public void addVertex(int vertex) {        adjList.putIfAbsent(vertex, new ArrayList<>());    }    // 添加有向边：from → to    public void addEdge(int from, int to) {        addVertex(from);        addVertex(to);        adjList.get(from).add(to);    }    // 打印图结构    public void printGraph() {        for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {            System.out.println("顶点 " + entry.getKey() +                              " 的邻接顶点: " + entry.getValue());        }    }    // 获取指定顶点的所有出边邻居    public List<Integer> getNeighbors(int vertex) {        return adjList.getOrDefault(vertex, new ArrayList<>());    }    // 主方法：测试示例    public static void main(String[] args) {        DirectedGraph graph = new DirectedGraph();                graph.addEdge(0, 1);        graph.addEdge(1, 2);        graph.addEdge(2, 0);        graph.addEdge(2, 3);                graph.printGraph();    }}  

代码解析

上面的代码实现了以下功能：

• addVertex：安全地添加顶点，避免重复。
• addEdge：添加一条从 from 指向 to 的有向边。
• printGraph：方便查看图的结构。
• getNeighbors：获取某个顶点的所有直接后继节点。

运行该程序，输出如下：

顶点 0 的邻接顶点: [1]顶点 1 的邻接顶点: [2]顶点 2 的邻接顶点: [0, 3]顶点 3 的邻接顶点: []  

扩展：常见图算法

掌握了基本的有向图数据结构后，你可以进一步学习以下经典算法：

• 深度优先搜索（DFS）：用于检测环、拓扑排序等。
• 广度优先搜索（BFS）：用于最短路径（无权图）。
• 拓扑排序：适用于任务依赖关系。
• Kosaraju算法：查找强连通分量。

总结

通过本教程，你已经学会了如何用Java构建一个简单的有向图，并理解了其核心操作。无论你是准备面试，还是学习Java图算法教程，这都是坚实的第一步。记住，实践是最好的老师——尝试自己添加删除边、检测环等功能，加深理解！

关键词回顾：Java有向图实现、有向图数据结构、Java图算法教程、有向图邻接表Java