数据结构与算法 / 系统课时
邻接矩阵
邻接矩阵
邻接矩阵用一个二维数组记录任意两个顶点之间是否存在边。它把“查边”变成一次下标访问,适合顶点数量稳定、边较密集或需要频繁判断连通关系的场景。本课将完成一个无向图实现,并用运行结果验证添加、查询和删除操作。
学习目标
- 理解邻接矩阵中行、列、顶点和边的对应关系。
- 掌握无向图的添加边、删除边、查边和枚举邻接点操作。
- 能根据图的密度与操作需求判断是否适合使用邻接矩阵。
问题定义
设图有 个顶点,为每个顶点分配一个下标。二维数组 matrix[i][j] 表示顶点 i 到顶点 j 的关系:无权图通常用 0 表示无边、用 1 表示有边;带权图可以保存权值,并额外约定一个值表示不存在边。
无向图中的一条边连接两个方向,因此添加边 (u, v) 时必须同时写入 matrix[u][v] 和 matrix[v][u]。有向图只写入前者。若允许自环,主对角线可能出现非零值;不允许自环时,主对角线保持为 0。
存储结构与操作成本
邻接矩阵固定占用 个单元,因此空间复杂度是 ,与实际边数无关。检查一条边只需访问一个数组元素,时间复杂度是 ;枚举某个顶点的所有邻接点需要扫描整行,时间复杂度是 。
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
判断 (u, v) 是否存在 |
直接读取 matrix[u][v] |
|
| 添加或删除一条边 | 无向图需要写两个对称位置 | |
枚举顶点 u 的邻接点 |
扫描第 u 行 |
|
| 存储空间 | 稀疏图中可能浪费大量单元 |

这张映射图体现了矩阵的关键性质:每一行代表起点,每一列代表终点;无向边会在主对角线两侧留下两个对称记录。
完整可运行示例
下面使用 Java 实现一个固定顶点集合的无向无权图。validateVertex 统一检查下标,避免数组越界;neighbors 扫描指定行并返回真实存在的邻接点。
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();
}
}预期输出
初始邻接矩阵:
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 同时表示“无边”,应使用额外布尔矩阵或明确的特殊值。
当图接近完全图、顶点数不大,或者算法需要大量执行“两个顶点是否相邻”的判断时,邻接矩阵通常很合适。对于顶点很多但边很少的稀疏图, 空间往往不经济,枚举邻接点也会扫描大量无效位置。
本课练习
- 将示例改为有向图,只写入
matrix[from][to],并验证A -> B存在但B -> A不存在。 - 为矩阵增加整数权值,要求支持添加带权边、查询权值,并使用一个不会与合法权值冲突的值表示无边。
- 实现
degree(int vertex),返回无向图中指定顶点的度,并用当前示例验证A的度在删除边前后分别为2和1。
本课总结
- 邻接矩阵用二维数组保存顶点对之间的关系,查边是 ,枚举邻接点是 。
- 无向图的矩阵应保持对称,添加和删除一条边都要更新两个位置。
- 空间使它更适合稠密图、顶点规模较小或查边频繁的任务。
下一课预告
下一课将学习“邻接表”,使用每个顶点自己的邻接集合只保存真实存在的边,并比较它与邻接矩阵在稀疏图中的空间和遍历成本。