数据结构与算法 / 系统课时

邻接矩阵

邻接矩阵

邻接矩阵用一个二维数组记录任意两个顶点之间是否存在边。它把“查边”变成一次下标访问,适合顶点数量稳定、边较密集或需要频繁判断连通关系的场景。本课将完成一个无向图实现,并用运行结果验证添加、查询和删除操作。

学习目标

  • 理解邻接矩阵中行、列、顶点和边的对应关系。
  • 掌握无向图的添加边、删除边、查边和枚举邻接点操作。
  • 能根据图的密度与操作需求判断是否适合使用邻接矩阵。

问题定义

设图有 VV 个顶点,为每个顶点分配一个下标。二维数组 matrix[i][j] 表示顶点 i 到顶点 j 的关系:无权图通常用 0 表示无边、用 1 表示有边;带权图可以保存权值,并额外约定一个值表示不存在边。

无向图中的一条边连接两个方向,因此添加边 (u, v) 时必须同时写入 matrix[u][v] 和 matrix[v][u]。有向图只写入前者。若允许自环,主对角线可能出现非零值;不允许自环时,主对角线保持为 0。

存储结构与操作成本

邻接矩阵固定占用 V×VV \times V 个单元,因此空间复杂度是 O(V2)O(V^2),与实际边数无关。检查一条边只需访问一个数组元素,时间复杂度是 O(1)O(1);枚举某个顶点的所有邻接点需要扫描整行,时间复杂度是 O(V)O(V)。

操作 时间复杂度 说明
判断 (u, v) 是否存在 O(1)O(1) 直接读取 matrix[u][v]
添加或删除一条边 O(1)O(1) 无向图需要写两个对称位置
枚举顶点 u 的邻接点 O(V)O(V) 扫描第 u 行
存储空间 O(V2)O(V^2) 稀疏图中可能浪费大量单元

邻接矩阵中顶点与二维数组的映射

这张映射图体现了矩阵的关键性质:每一行代表起点,每一列代表终点;无向边会在主对角线两侧留下两个对称记录。

完整可运行示例

下面使用 Java 实现一个固定顶点集合的无向无权图。validateVertex 统一检查下标,避免数组越界;neighbors 扫描指定行并返回真实存在的邻接点。

java
import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;

public class AdjacencyMatrixDemo {

    private final String[] vertices;
    private final int[][] matrix;

    public AdjacencyMatrixDemo(String[] vertices) {
        this.vertices = vertices.clone();
        this.matrix = new int[vertices.length][vertices.length];
    }

    public void addUndirectedEdge(int from, int to) {
        validateVertex(from);
        validateVertex(to);
        matrix[from][to] = 1;
        matrix[to][from] = 1;
    }

    public void removeUndirectedEdge(int from, int to) {
        validateVertex(from);
        validateVertex(to);
        matrix[from][to] = 0;
        matrix[to][from] = 0;
    }

    public boolean hasEdge(int from, int to) {
        validateVertex(from);
        validateVertex(to);
        return matrix[from][to] == 1;
    }

    public List<String> neighbors(int vertex) {
        validateVertex(vertex);
        List<String> result = new ArrayList<>();

        for (int i = 0; i < matrix[vertex].length; i++) {
            if (matrix[vertex][i] == 1) {
                result.add(vertices[i]);
            }
        }
        return result;
    }

    public void printMatrix() {
        System.out.println("  " + String.join(" ", vertices));

        for (int i = 0; i < matrix.length; i++) {
            StringJoiner row = new StringJoiner(" ");
            for (int value : matrix[i]) {
                row.add(String.valueOf(value));
            }
            System.out.println(vertices[i] + " " + row);
        }
    }

    private void validateVertex(int vertex) {
        if (vertex < 0 || vertex >= vertices.length) {
            throw new IllegalArgumentException("顶点下标越界: " + vertex);
        }
    }

    public static void main(String[] args) {
        String[] vertices = {"A", "B", "C", "D"};
        AdjacencyMatrixDemo graph = new AdjacencyMatrixDemo(vertices);

        graph.addUndirectedEdge(0, 1);
        graph.addUndirectedEdge(0, 2);
        graph.addUndirectedEdge(1, 3);
        graph.addUndirectedEdge(2, 3);

        System.out.println("初始邻接矩阵:");
        graph.printMatrix();
        System.out.println("A 与 D 相邻: " + graph.hasEdge(0, 3));
        System.out.println("A 的邻接点: " + graph.neighbors(0));

        graph.removeUndirectedEdge(0, 2);
        System.out.println("删除 A-C 后:");
        graph.printMatrix();
    }
}

预期输出

text
初始邻接矩阵:
  A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
A 与 D 相邻: false
A 的邻接点: [B, C]
删除 A-C 后:
  A B C D
A 0 1 0 0
B 1 0 0 1
C 0 0 0 1
D 0 1 1 0

边界与适用场景

顶点下标必须处于 0 到 V - 1。对于无向图,添加和删除时若只更新一个位置,矩阵会失去对称性,后续从不同方向查询同一条边将得到矛盾结果。若边权可能等于 0,就不能再用 0 同时表示“无边”,应使用额外布尔矩阵或明确的特殊值。

当图接近完全图、顶点数不大,或者算法需要大量执行“两个顶点是否相邻”的判断时,邻接矩阵通常很合适。对于顶点很多但边很少的稀疏图,O(V2)O(V^2) 空间往往不经济,枚举邻接点也会扫描大量无效位置。

本课练习

  1. 将示例改为有向图,只写入 matrix[from][to],并验证 A -> B 存在但 B -> A 不存在。
  2. 为矩阵增加整数权值,要求支持添加带权边、查询权值,并使用一个不会与合法权值冲突的值表示无边。
  3. 实现 degree(int vertex),返回无向图中指定顶点的度,并用当前示例验证 A 的度在删除边前后分别为 2 和 1。

本课总结

  • 邻接矩阵用二维数组保存顶点对之间的关系,查边是 O(1)O(1),枚举邻接点是 O(V)O(V)。
  • 无向图的矩阵应保持对称,添加和删除一条边都要更新两个位置。
  • O(V2)O(V^2) 空间使它更适合稠密图、顶点规模较小或查边频繁的任务。

下一课预告

下一课将学习“邻接表”,使用每个顶点自己的邻接集合只保存真实存在的边,并比较它与邻接矩阵在稀疏图中的空间和遍历成本。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

邻接矩阵

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通