邻接矩阵存储 · 融合风（象牙 + Obsidian 入口）

速查

邻接矩阵：$A[i][j]=1$ 有边、0 无边。空间 O(n²)（与边数无关），适合稠密图；判断边 O(1)，求度 O(n)；无向图矩阵对称；$A^k[i][j]$ = 长度为 k 的路径数。

核心概念 ▾

邻接矩阵用 $n\times n$ 二维数组表示 n 个顶点间的邻接关系。无权图：$A[i][j]=1$ 若 $(v_i,v_j)\in E$，否则 0。带权图（网）：$A[i][j]=w_{ij}$ 有边、$\infty$ 无边、对角 0。

#define MaxVertexNum 100
typedef struct {
    char Vex[MaxVertexNum];                    // 顶点表
    int Edge[MaxVertexNum][MaxVertexNum];      // 邻接矩阵
    int vexnum, arcnum;                        // 顶点数、边数
} MGraph;

特点无向图矩阵对称，可只存上三角；第 i 行（列）1 的个数 = $v_i$ 的度（无向图）；有向图第 i 行 1 的个数 = 出度 OD($v_i$)、第 i 列 = 入度 ID($v_i$)。空间恒为 O(n²)，适合稠密图。

关键性质 ▾

性质	说明
空间复杂度	O(n²)，与边数无关
求度	无向图：行之和=度；有向图：行之和=出度、列之和=入度
判断边存在	O(1) 直接查表
适用稠密图	边数接近 n² 时空间利用率高
适用稀疏图	大量 0 浪费空间，不如邻接表
无向图对称性	$A[i][j] = A[j][i]$

邻接矩阵的幂 ▾

$A^k$ 中 $A^k[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 长度为 k 的路径数，用于求两点间特定长度的路径数目。

常见考法 ▾

考法	解题套路
写出邻接矩阵	根据边集填 0/1 矩阵
从矩阵求度	行之和（出度）+ 列之和（入度）
求路径数	$A^k[i][j]=$ 长度为 k 的路径数
选存储	稀疏→邻接表，稠密→邻接矩阵
判断边	O(1) 直接查 $A[i][j]$

易错点 ▾

易错清单

⚠️ 空间始终 O(n²)，稀疏图浪费严重。
⚠️ 无向图对称，有向图不一定对称。
⚠️ 网的对角线是 0 不是 $\infty$。
⚠️ 求度的时间是 O(n)，不是 O(1)。
⚠️ 同一图不同顶点编号 → 不同矩阵，但本质相同。

核心结论 ▾

邻接矩阵适合稠密图，空间 O(n²)。
判断边存在 O(1)，求度 O(n)。
无向图矩阵对称，可压缩存储。
$A^k[i][j]$ 表示 i 到 j 长度为 k 的路径数。
同一图不同编号→不同矩阵，但本质相同。

记忆卡片 ▾

邻接矩阵的空间复杂度？

O(n²)，与边数无关。

无向图矩阵有什么特点？

对称矩阵，第 i 行之和 = 顶点 $v_i$ 的度。

有向图如何求出入度？

出度 = 第 i 行之和，入度 = 第 i 列之和。

$A^k[i][j]$ 表示什么？

从 i 到 j 长度为 k 的路径数目。

交互动画 · 矩阵 + 加边 ▾

5 顶点无向图 → 对称邻接矩阵 A

点按钮：高亮行/列求度、或动态加边（联动更新对称两项）

求度 = 数某行 1 的个数（O(n)）；加边须同时更新 $A[i][j]$ 与 $A[j][i]$（对称性）。

核心概念 ▾

关键性质 ▾

邻接矩阵的幂 ▾

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 矩阵 + 加边 ▾

相关知识点