Java邻接表详解（从零开始掌握图的邻接表表示法）

为什么选择Java实现邻接表？

Java语言具有良好的面向对象特性、丰富的集合框架（如 ArrayList、LinkedList），非常适合用来构建图的数据结构。通过本教程，你将掌握Java邻接表的核心思想与编码技巧。

步骤一：定义图的基本结构

我们首先创建一个 Graph 类，使用 ArrayList<List<Integer>> 来存储邻接表。每个索引代表一个顶点，其对应的列表存储与之相连的顶点。

import java.util.*;public class Graph {    private int vertices; // 顶点数量    private List<List<Integer>> adjList; // 邻接表    // 构造函数    public Graph(int vertices) {        this.vertices = vertices;        adjList = new ArrayList<>(vertices);                // 初始化每个顶点的邻接列表        for (int i = 0; i < vertices; i++) {            adjList.add(new ArrayList<>());        }    }}

步骤二：添加边（建立连接）

在无向图中，如果顶点 A 和 B 相连，那么 A 的邻接表要包含 B，B 的邻接表也要包含 A。如果是有向图，则只需单向添加。

// 添加无向边public void addEdge(int u, int v) {    adjList.get(u).add(v);    adjList.get(v).add(u); // 如果是有向图，删除这一行}// 添加有向边（可选）public void addDirectedEdge(int u, int v) {    adjList.get(u).add(v);}

步骤三：打印邻接表

为了验证我们的邻接表是否正确构建，可以编写一个打印方法：

public void printGraph() {    for (int i = 0; i < vertices; i++) {        System.out.print("顶点 " + i + " 的邻接顶点: ");        for (int neighbor : adjList.get(i)) {            System.out.print(neighbor + " ");        }        System.out.println();    }}

完整示例：构建并打印一个简单图

下面是一个完整的测试程序，演示如何使用我们刚刚创建的 Graph 类：

public class Main {    public static void main(String[] args) {        // 创建一个包含5个顶点的图        Graph graph = new Graph(5);                // 添加边        graph.addEdge(0, 1);        graph.addEdge(0, 4);        graph.addEdge(1, 2);        graph.addEdge(1, 3);        graph.addEdge(1, 4);        graph.addEdge(2, 3);        graph.addEdge(3, 4);                // 打印邻接表        graph.printGraph();    }}

运行结果将输出每个顶点及其相邻顶点，例如：

顶点 0 的邻接顶点: 1 4 顶点 1 的邻接顶点: 0 2 3 4 顶点 2 的邻接顶点: 1 3 顶点 3 的邻接顶点: 1 2 4 顶点 4 的邻接顶点: 0 1 3

进阶：支持泛型顶点（如字符串）

如果你希望顶点不是整数而是字符串（如城市名），可以使用 Map<String, List<String>> 来实现更灵活的邻接表。这属于Java图数据结构的高级应用，有兴趣的同学可以自行探索。

总结

通过本教程，你已经学会了如何用 Java 实现图的邻接表表示。邻接表不仅节省内存，而且便于遍历邻居节点，是图算法（如DFS、BFS、Dijkstra等）的基础。掌握邻接表实现教程中的核心思想，将为你后续学习图论算法打下坚实基础。

记住，实践是最好的老师！建议你动手敲一遍代码，并尝试修改为有向图或添加权重支持。祝你在Java邻接表的学习之旅中收获满满！