Java邻接矩阵详解（小白也能学会的图数据结构表示方法）

邻接矩阵的优缺点

优点：

• 查询两个顶点是否相邻的时间复杂度为 O(1)。
• 实现简单，逻辑清晰。

缺点：

• 空间复杂度为 O(n²)，对于稀疏图（边很少）来说浪费大量内存。
• 添加或删除顶点需要重建整个矩阵。

用Java实现邻接矩阵

下面我们用Java语言编写一个简单的邻接矩阵类，支持添加边、打印矩阵等基本操作。

public class AdjacencyMatrix {    private int[][] matrix;    private int vertices;    // 构造函数：初始化邻接矩阵    public AdjacencyMatrix(int vertices) {        this.vertices = vertices;        matrix = new int[vertices][vertices];        // 初始化所有元素为0（表示无边）        for (int i = 0; i < vertices; i++) {            for (int j = 0; j < vertices; j++) {                matrix[i][j] = 0;            }        }    }    // 添加一条无向边    public void addEdge(int start, int end) {        if (start >= 0 &&& start < vertices && end >= 0 && end < vertices) {            matrix[start][end] = 1;            matrix[end][start] = 1; // 无向图：对称        } else {            System.out.println("顶点索引超出范围！");        }    }    // 打印邻接矩阵    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();        }    }    // 主方法：测试示例    public static void main(String[] args) {        AdjacencyMatrix graph = new AdjacencyMatrix(4);        graph.addEdge(0, 1);        graph.addEdge(0, 2);        graph.addEdge(1, 2);        graph.addEdge(2, 3);        System.out.println("邻接矩阵表示：");        graph.printMatrix();    }}  

代码说明

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

• AdjacencyMatrix(int vertices)：构造函数，创建一个 vertices × vertices 的二维数组，并初始化为0。
• addEdge(int start, int end)：添加一条无向边。注意我们同时设置 matrix[start][end] 和 matrix[end][start] 为1，因为是无向图。
• printMatrix()：遍历并打印整个邻接矩阵。

运行上述代码，输出结果如下：

邻接矩阵表示：0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0   

扩展思考

如果你要处理有权图，只需将 matrix[i][j] 赋值为具体的权重（如距离、成本等），而不是简单的0或1。此外，对于有向图，添加边时只需设置 matrix[start][end] = 1，无需对称赋值。

总结

通过本教程，你已经掌握了如何使用Java邻接矩阵来表示图结构。这是学习更高级图算法（如深度优先搜索、广度优先搜索、Dijkstra最短路径等）的基础。希望这篇数据结构教程能帮助你打下坚实的基础！

关键词回顾：Java邻接矩阵、图的表示方法、邻接矩阵实现、数据结构教程。