Java邻接矩阵顶点删除实现咨询：现有两种思路求指导

嘿，针对你这个用Java实现邻接矩阵时的顶点删除问题，我来帮你理清楚两种思路的优劣，再给出具体的实现建议～

你已经完成了删除顶点所有边的操作，接下来的核心是处理顶点本身在ArrayList和邻接矩阵中的存在形式：

思路1：将ArrayList对应位置设为null #

这种方式是直接把要删除的顶点在ArrayList中的位置置为null，邻接矩阵保持原大小不变。

• 优点：操作极快，时间复杂度O(1)，不用改动矩阵的结构，适合对性能要求极高且删除非常频繁的场景。
• 缺点：会引入大量冗余的null值，后续所有操作（比如遍历顶点、查找顶点索引、统计顶点数量）都要额外做null判断，很容易遗漏导致NullPointerException；而且矩阵的行数/列数和实际有效顶点数不匹配，维护起来会越来越繁琐。

思路2：重建ArrayList和邻接矩阵 #

这种方式是彻底移除目标顶点，然后重新创建顶点列表和对应的邻接矩阵。

• 优点：结构非常干净，ArrayList中全是有效顶点，矩阵大小和实际顶点数完全匹配，后续操作逻辑简单，几乎不会引入额外的bug，维护成本极低。
• 缺点：时间复杂度是O(n²)（需要复制原矩阵中除目标行/列外的所有元素），如果是超大图且频繁执行删除操作，性能会有一定损耗。

如果你的图规模不大，或者删除操作不是特别频繁，我强烈推荐用重建的方式，下面是具体的代码实现：

import java.util.ArrayList;

public class AdjacencyMatrixGraph {
    // 存储顶点标签的ArrayList
    private ArrayList<Character> vertices;
    // 邻接矩阵：matrix[i][j]为true表示顶点i和顶点j之间有边
    private boolean[][] adjacencyMatrix;

    // 构造方法：初始化顶点列表和空矩阵
    public AdjacencyMatrixGraph() {
        vertices = new ArrayList<>();
        adjacencyMatrix = new boolean[0][0];
    }

    // 添加顶点的方法（示例）
    public void addVertex(char vertex) {
        vertices.add(vertex);
        // 扩展矩阵大小
        int newSize = vertices.size();
        boolean[][] newMatrix = new boolean[newSize][newSize];
        // 复制原矩阵内容
        for (int i = 0; i < newSize - 1; i++) {
            System.arraycopy(adjacencyMatrix[i], 0, newMatrix[i], 0, newSize - 1);
        }
        adjacencyMatrix = newMatrix;
    }

    // 删除顶点的核心方法
    public void deleteVertex(char targetVertex) {
        // 先找到目标顶点在ArrayList中的索引
        int targetIndex = vertices.indexOf(targetVertex);
        if (targetIndex == -1) {
            throw new IllegalArgumentException("要删除的顶点不存在");
        }

        // 步骤1：移除该顶点的所有边（你已经完成这步，这里可以再次确认）
        for (int i = 0; i < vertices.size(); i++) {
            adjacencyMatrix[targetIndex][i] = false;
            adjacencyMatrix[i][targetIndex] = false;
        }

        // 步骤2：重建顶点列表，过滤掉目标顶点
        ArrayList<Character> newVertices = new ArrayList<>();
        for (int i = 0; i < vertices.size(); i++) {
            if (i != targetIndex) {
                newVertices.add(vertices.get(i));
            }
        }

        // 步骤3：重建邻接矩阵，复制原矩阵中除目标行/列外的所有元素
        int newSize = newVertices.size();
        boolean[][] newMatrix = new boolean[newSize][newSize];
        for (int i = 0; i < vertices.size(); i++) {
            if (i == targetIndex) continue; // 跳过目标行
            for (int j = 0; j < vertices.size(); j++) {
                if (j == targetIndex) continue; // 跳过目标列
                // 计算新矩阵中的索引：如果原索引在目标索引前，保持不变；否则减1
                int newRow = i < targetIndex ? i : i - 1;
                int newCol = j < targetIndex ? j : j - 1;
                newMatrix[newRow][newCol] = adjacencyMatrix[i][j];
            }
        }

        // 更新类的成员变量
        this.vertices = newVertices;
        this.adjacencyMatrix = newMatrix;
    }

    // 打印矩阵的方法（用于测试）
    public void printMatrix() {
        System.out.println("顶点列表：" + vertices);
        System.out.println("邻接矩阵：");
        for (boolean[] row : adjacencyMatrix) {
            for (boolean val : row) {
                System.out.print(val + "\t");
            }
            System.out.println();
        }
    }

    // 测试示例
    public static void main(String[] args) {
        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph();
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        // 添加边A-B、A-C
        graph.adjacencyMatrix[0][1] = true;
        graph.adjacencyMatrix[1][0] = true;
        graph.adjacencyMatrix[0][2] = true;
        graph.adjacencyMatrix[2][0] = true;

        System.out.println("删除前的图：");
        graph.printMatrix();

        graph.deleteVertex('A');

        System.out.println("\n删除后的图：");
        graph.printMatrix();
    }
}

• 若图规模小或删除不频繁：优先选重建方式，结构清晰易维护。
• 若图规模极大且删除频繁：可以考虑用null占位，但一定要在所有操作顶点的逻辑中加入null判断，比如自定义查找顶点索引的方法时跳过null，遍历顶点时过滤null值。

内容的提问来源于stack exchange，提问作者YI YANG