📐 408 矩阵压缩存储与稀疏矩阵(含稀疏图对比)终极笔记

核心痛点解决

矩阵压缩下标计算极易差 1(下标从 0 还是从 1 开始?行优先还是列优先?),稀疏矩阵与稀疏图的存储结构常在选择题中混考。 本笔记采用 【不背公式现场推导法 + 可折叠手算例子 + 题眼破局 + 避坑指南】,保证考场上算下标、选结构 100% 零失误。


一、 稀疏矩阵的压缩存储(你的真题图片核心考点)

一句话记忆

“稀疏矩阵只存非零元,失去随机存取特性;除三元组外,必须额外存【总行数、总列数、非零元总个数】”。

1. 什么是稀疏矩阵?

矩阵中非零元素的个数 远远小于矩阵元素的总数 (通常认为稠密度 ),且非零元素分布没有规律。

2. 两种存储结构对比(408 选择题必考)

三元组顺序表 vs 十字链表

存储结构存储方式核心结构组成适用场景随机存取?
三元组表(顺序存储)把每个非零元存为 (行标 i, 列标 j, 值 v),按行优先排列三元组数组 + 矩阵总行数 、总列数 、非零元个数 矩阵转置、静态查阅❌ 丧失随机存取特性(需顺序遍历查找)
十字链表(链式存储)每个非零元是一个结点,同时处于所在行循环链表和列循环链表中结点含 5 个域:row, col, val, right, down + 行/列头指针数组频繁插入、删除非零元(如矩阵加减法 )❌ 不能随机存取

408 核心防坑指南(直击你发的图片真题!)

为什么三元组表必须额外保存“矩阵的总行数”和“总列数”?

  • 假设一个 的稀疏矩阵,第 9 行和第 10 行全都是 0(没有任何非零元素)。
  • 那么在三元组表中,行标 i 最大只会出现到 8!如果不额外记录“矩阵总行数为 10、总列数为 10”,当你试图把这个三元组还原成原矩阵时,你根本不知道原矩阵到底是 还是 !
  • 至于“包含非零元素的行数/列数”,直接扫描一遍三元组表就能统计出来,不需要额外保存。

二、 特殊矩阵的压缩存储(下标计算必杀技)

考场零失误心法(千万别死背公式!)

408 算一维数组下标 k,永远只用两步**“数人头法”**:

  1. 算排在 A[i][j] 前面的元素一共有多少个(记为 Count):
    • Count = 前面完整行(或列)的元素总数 + 当前行(或列)排在它前面的元素个数。
  2. 看一维数组 B[k] 的起始下标:
    • 若 B 从 0 开始:k = Count
    • 若 B 从 1 开始:k = Count + 1

1. 二维数组普通存储( 行 列,设行列下标从 0 开始,B 从 0 开始)

  • 行优先:前面有 整行(每行 个),当前行前面有 个 。
  • 列优先:前面有 整列(每列 个),当前列前面有 个 。

2. 对称矩阵( 阶,,行列下标从 1 开始)

压缩策略:只存下三角(含主对角线),共 个元素

核心铁律:

  • 如果题目默认行优先存下三角():
    • 当给你的元素满足 (在下三角):直接算前面有 i-1 行(元素数为 ),当前行前面有 j-1 个元素 。
    • 当给你的元素是 (在上三角):因为对称矩阵 ,第一步必须先把 i 和 j 互换,折算到下三角再代公式!

变体预警(列优先陷阱!)

如果题目改成**“按列优先存储下三角”**(或行优先存储上三角):

  • 下三角第 1 列有 个元素,第 2 列有 个……第 列有 个!
  • 遇到这种题千万别背公式,直接在草稿纸上画个 的小矩阵,标上第 1 列 个、第 2 列 个,把前 列加起来即可!

3. 三角矩阵(上三角 / 下三角,常量区占最后 1 个位置)

与对称矩阵的唯一区别

  • 三角矩阵另一半全都是同一个常数 (比如全为 0)。
  • 一维数组长度比对称矩阵多 1 个位置:共 个空间,最后一个位置专门用来存那个常数 !
  • 下标计算与对称矩阵完全一致(但在非压缩区直接返回最后一个下标 或 )。

4. 三对角矩阵(带状矩阵,)—— 考察频率:⭐⭐⭐⭐

一句话记忆

“首尾两行各 2 个,中间每行都 3 个;前向公式 2i + j - 3(从 0 起)”。

双向推导公式(设矩阵行列 从 1 开始)

① 已知 A[i][j] 求一维下标 k(按行优先):

  • 前面有 i-1 行:第 1 行 2 个,其余 i-2 行每行 3 个 前 i-1 行共有 个元素。
  • 第 i 行有 A[i][i-1], A[i][i], A[i][i+1],因此 A[i][j] 前面有 j - (i - 1) = j - i + 1 个元素。
  • 前面元素总数 。
    • 若 B 从 0 开始:
    • 若 B 从 1 开始:

② 已知一维下标 k 反求矩阵行列 (i, j)(选择题秒杀神技):

  • 考场最快做法:根本不用记整除取模公式!直接把选项里的 (i, j) 代入上面的正向公式 2i + j - 3(或 -2),算出来等于题目给的 k 直接秒选!

三、 稀疏图 vs 稠密图:矩阵与链表存储全对比(联动《图论核心算法》)

为什么要把“稀疏矩阵”和“稀疏图”放在一起看?

当一个图是稀疏图(边数 )时,它的邻接矩阵就是一个典型的稀疏矩阵! 如果直接用二维数组(邻接矩阵)存稀疏图,会浪费海量的 0 或 ∞ 空间,且遍历一个点的所有邻居需要空扫整行 。因此稀疏图必须改用链式压缩结构(邻接表、十字链表、邻接多重表)!

1. 图的 4 大存储结构全景对比表(408 必背)

存储结构适用图类型空间复杂度找某点所有邻居判两点是否有边删边/操作特点
邻接矩阵稠密图(有向/无向均可)(只与顶点数有关,与边数无关)(最快)无向图的邻接矩阵一定是对称矩阵,可压缩存储!
邻接表稀疏图(有向/无向均可)无向:
有向:
有向图求入度难(需遍历全表,或建逆邻接表);表示不唯一
十字链表有向稀疏图完美结合邻接表与逆邻接表,求入度、出度都极快(也是稀疏矩阵的链式存储结构!)
邻接多重表无向稀疏图(一条边只存 1 个结点!)解决无向图邻接表中“一条边存两份、删边需找两个结点”的痛点

408 极易混淆的两大高频考点

考点 1:邻接矩阵 (矩阵乘法)的图论物理意义!(2012/2021 真题)

  • 设图 的邻接矩阵为 (无权图,有边为 1,无边为 0),则矩阵幂 中的元素 的值,等于从顶点 到顶点 长度为 的路径的总条数!

考点 2:拓扑排序 + 邻接矩阵 = 三角矩阵!(2016/2022 真题)

  • 若一个有向图(DAG)存在拓扑序列,且顶点的编号恰好按拓扑有序排列(即每条有向边都从小编号指向大编号,),那么该图的邻接矩阵必定是一个上三角矩阵(主对角线及以下全为 0)!
  • 反之,若一个有向图的邻接矩阵是三角矩阵(主对角线全为 0 的上三角或下三角),则该图必定没有环(一定存在拓扑序列)!

2. 图论核心算法在【邻接矩阵(稠密图)】vs【邻接表(稀疏图)】下的复杂度对照

背完这张表,408 图论复杂度题一分不丢

算法 / 操作邻接矩阵(适合稠密图)邻接表(适合稀疏图)408 考场核心结论
DFS / BFS 遍历遍历每个点都要扫描其所有边,矩阵必须扫满整行
拓扑排序 / 关键路径本质基于 DFS 或 BFS(入度表),复杂度同遍历
Prim(最小生成树)(配合堆)408 默认考朴素 Prim,时间复杂度 与边数无关,专治稠密图
Kruskal(最小生成树)—按边排序 + 并查集,时间只与边数 有关,专治稀疏图
Dijkstra(单源最短路)(配合堆)408 默认考朴素版 ;若求所有点对执行 次则为
Floyd(多源最短路)不适用(直接用矩阵)三重循环固定

📝 历年真题精选(实战演练·破局版)

真题 1(特殊矩阵压缩 · 对称矩阵列优先陷阱)

题目:设有一个 12×12 的对称矩阵 ,将其上三角部分的元素 ()按列优先存入 C 语言的一维数组 中,元素 在 中的下标是( )。 A. 15 B. 20 C. 21 D. 22

真题 2(图的邻接矩阵与三角矩阵 · 2016 年 408 真题)

题目:若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是( )。 A. 存在,且唯一 B. 存在,且不唯一 C. 存在,可能不唯一 D. 无法确定是否存在

真题 3(稀疏矩阵存储结构选择)

题目:对稀疏矩阵进行压缩存储后,失去了( )特性;若需要对稀疏矩阵进行频繁的加法运算(非零元素个数和位置动态变化),最适合采用的存储结构是( )。 A. 随机存取,三元组表 B. 随机存取,十字链表 C. 顺序存取,三元组表 D. 散列存取,邻接多重表