Java如何用邻接矩阵存储图

在计算机科学中，图是一种非常重要的数据结构，用于表示对象之间的关系。图由顶点（节点）和边组成，边连接两个顶点。图的存储方式有多种，其中邻接矩阵是一种常见的存储方式。本文将介绍如何在Java中使用邻接矩阵来存储图。

邻接矩阵简介

邻接矩阵是一个二维数组，用于表示图中顶点之间的连接关系。假设图中有n个顶点，那么邻接矩阵就是一个n x n的矩阵。矩阵中的每个元素matrix[i][j]表示顶点i和顶点j之间是否存在边。如果存在边，则matrix[i][j]为1（或边的权重），否则为0。

无向图的邻接矩阵

对于无向图，邻接矩阵是对称的。因为如果顶点i和顶点j之间存在边，那么顶点j和顶点i之间也存在边。因此，matrix[i][j] = matrix[j][i]。

有向图的邻接矩阵

对于有向图，邻接矩阵不一定对称。因为如果顶点i指向顶点j，那么matrix[i][j] = 1，但matrix[j][i]不一定为1。

Java实现邻接矩阵

下面是一个简单的Java代码示例，展示如何使用邻接矩阵来存储图。

public class Graph {
    private int[][] adjacencyMatrix;
    private int numVertices;

    // 构造函数，初始化邻接矩阵
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
    }

    // 添加边
    public void addEdge(int i, int j) {
        adjacencyMatrix[i][j] = 1;
        adjacencyMatrix[j][i] = 1; // 对于无向图，需要对称设置
    }

    // 删除边
    public void removeEdge(int i, int j) {
        adjacencyMatrix[i][j] = 0;
        adjacencyMatrix[j][i] = 0; // 对于无向图，需要对称设置
    }

    // 检查是否存在边
    public boolean hasEdge(int i, int j) {
        return adjacencyMatrix[i][j] == 1;
    }

    // 打印邻接矩阵
    public void printMatrix() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5); // 创建一个有5个顶点的图

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        graph.printMatrix();
    }
}

代码解释

1. 构造函数：Graph(int numVertices) 初始化了一个大小为numVertices x numVertices的邻接矩阵，所有元素初始值为0。

2. 添加边：addEdge(int i, int j) 方法在顶点i和顶点j之间添加一条边。对于无向图，需要同时设置matrix[i][j]和matrix[j][i]。

3. 删除边：removeEdge(int i, int j) 方法删除顶点i和顶点j之间的边。同样，对于无向图，需要同时设置matrix[i][j]和matrix[j][i]为0。

4. 检查边：hasEdge(int i, int j) 方法检查顶点i和顶点j之间是否存在边。

5. 打印邻接矩阵：printMatrix() 方法打印当前的邻接矩阵。

运行结果

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

0 1 1 0 0 
1 0 0 1 0 
1 0 0 0 1 
0 1 0 0 0 
0 0 1 0 0 

这个输出表示了一个有5个顶点的无向图的邻接矩阵。矩阵中的1表示两个顶点之间存在边，0表示不存在边。

总结

邻接矩阵是一种简单直观的图存储方式，特别适用于稠密图（即边数接近顶点数的平方）。对于稀疏图（边数远小于顶点数的平方），邻接矩阵可能会浪费大量空间。在这种情况下，邻接表可能是更好的选择。

通过本文的介绍和代码示例，你应该已经掌握了如何在Java中使用邻接矩阵来存储图。希望这对你理解和实现图算法有所帮助！