Appearance
邻接矩阵
为什么需要邻接矩阵
图由顶点集和边集组成，要在计算机中处理图，首先需要解决的问题就是如何存储图的结构信息。邻接矩阵是最直观、最经典的图存储方式——用一个二维数组来记录顶点之间的连接关系。
邻接矩阵的思路非常简单：如果图有 n 个顶点，就用一个 n×n 的矩阵 A，其中 A[i][j] 表示顶点 i 到顶点 j 是否存在边（或边的权值）。408 考研中，邻接矩阵是图存储结构的基础，也是理解邻接表优缺点的参照物。
核心思想
邻接矩阵的核心特点：
- 二维数组直接映射：用
A[i][j]表示顶点 i 与顶点 j 之间的关系 - 无权图：
A[i][j] = 1表示存在边，A[i][j] = 0表示不存在边 - 带权图：
A[i][j] = w表示边的权值，A[i][j] = ∞表示不存在边 - 无向图的对称性：无向图的邻接矩阵是对称矩阵，即
A[i][j] = A[j][i]
无向图示例（4 个顶点）：
图: 0 — 1 邻接矩阵:
| | 0 1 2 3
3 — 2 0 [0, 1, 0, 1]
1 [1, 0, 1, 0]
2 [0, 1, 0, 1]
3 [1, 0, 1, 0]有向图示例（边 0→1, 0→2, 2→1）：
邻接矩阵:
0 1 2
0 [0, 1, 1]
1 [0, 0, 0]
2 [0, 1, 0]注意：有向图的邻接矩阵不一定对称。
交互可视化
通过下方的交互动画，你可以逐步观察邻接矩阵的执行过程：
操作详解
存储结构
邻接矩阵的 C 语言定义：
c
#define MaxVertexNum 100 // 最大顶点数
#define INFINITY 65535 // 表示无穷大（用于带权图）
// 无权图
typedef struct {
char vex[MaxVertexNum]; // 顶点表
int edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵（0/1）
int vexNum, edgeNum; // 顶点数、边数
} MGraph;
// 带权图
typedef struct {
char vex[MaxVertexNum];
int edge[MaxVertexNum][MaxVertexNum]; // 权值，无边时为 INFINITY
int vexNum, edgeNum;
} WGraph;初始化与建图：
c
// 初始化无向无权图
void initGraph(MGraph *G, int n) {
G->vexNum = n;
G->edgeNum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
G->edge[i][j] = 0;
}
// 添加无向边
void addEdge(MGraph *G, int u, int v) {
G->edge[u][v] = 1;
G->edge[v][u] = 1; // 无向图需对称赋值
G->edgeNum++;
}带权图的邻接矩阵初始化时，将所有元素设为 INFINITY，对角线设为 0。
度的计算
无向图：顶点 i 的度 = 第 i 行（或第 i 列）中非零元素的个数。
c
// 无向图求顶点 i 的度
int degree(MGraph *G, int i) {
int d = 0;
for (int j = 0; j < G->vexNum; j++)
if (G->edge[i][j] != 0)
d++;
return d;
}有向图：
| 类型 | 计算方法 |
|---|---|
| 出度 OD(i) | 第 i 行非零元素个数 |
| 入度 ID(i) | 第 i 列非零元素个数 |
| 度 TD(i) | OD(i) + ID(i) |
c
// 有向图求顶点 i 的出度和入度
void directedDegree(MGraph *G, int i, int *outD, int *inD) {
*outD = *inD = 0;
for (int j = 0; j < G->vexNum; j++) {
if (G->edge[i][j] != 0) (*outD)++; // 第 i 行 → 出度
if (G->edge[j][i] != 0) (*inD)++; // 第 i 列 → 入度
}
}优缺点分析
| 优点 | 缺点 |
|---|---|
判断两顶点是否相邻：O(1)，直接访问 A[i][j] | 空间复杂度 O(V²)，稀疏图浪费严重 |
| 实现简单，适合稠密图 | 统计边数需遍历整个矩阵，O(V²) |
| 方便计算矩阵运算（如求路径数） | 增删顶点不灵活，需调整矩阵大小 |
| 无向图可压缩存储（对称矩阵只存上/下三角） | 找某顶点所有邻接点需扫描一整行，O(V) |
适用场景：顶点数不多、边数较多的稠密图。当边数远小于 V² 时（稀疏图），应优先考虑邻接表。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 判断边是否存在 | O(1) | 直接访问 A[i][j] |
| 求某顶点的度 | O(V) | 遍历一行（或一列） |
| 求所有边数 | O(V²) | 遍历整个矩阵 |
| 插入/删除一条边 | O(1) | 修改矩阵元素 |
| 插入/删除一个顶点 | O(V²) | 需调整矩阵结构 |
空间复杂度：O(V²)，无论图是稠密还是稀疏都需要 V×V 的存储空间。
考研高频考点
- ⭐ 无向图邻接矩阵的对称性（选择题/判断题高频）
- ⭐ 从邻接矩阵求顶点的度/出度/入度（填空题必考）
- ⭐ 邻接矩阵 vs 邻接表的优缺点对比（简答题高频）
- ⭐ 邻接矩阵的空间复杂度 O(V²) 及适用场景（概念题）
- 带权图邻接矩阵中 ∞ 和 0 的含义区分（易错点）
- 邻接矩阵 A 的幂次 Aⁿ[i][j] 表示顶点 i 到 j 长度为 n 的路径条数（偶尔考）