🕸️ 408 图的四大存储结构终极拆解(邻接矩阵 / 邻接表 / 十字链表 / 邻接多重表)
核心痛点解决
为什么无向图有邻接表还要搞个“邻接多重表”?为什么有向图有邻接表还要搞个“十字链表”?每个结点到底有几个指针域? 本笔记把四大结构的 【物理结构图解 + C 语言结构体代码 + 结点/边数计算公式 + 痛点演进关系 + 408 真题破局】 彻底讲透,保证选择题与代码大题 0 失误!
🧭 0. 一张图看懂四大存储结构的“演进逻辑”(必背心法)
为什么会有这 4 种结构?(按“解决痛点”记忆,永不混淆)
- 邻接矩阵(二维数组):最直观,判边 。但遇到稀疏图(边极少)时,满屏都是
0或∞,空间浪费极大,找邻居还要空扫整行 。- 邻接表(数组 + 单链表):为了救稀疏图而生!只存实际存在的边。但它暴露出两个致命痛点:
- 痛点 A(针对有向图):顺着链表只能算出度;想求某点的入度,必须把整个图所有链表全扫一遍!
- 痛点 B(针对无向图):一条无向边 会在 和 的链表里各存一次(共 2 个边结点);如果要删除一条边,得去两个链表里分别找并删除,极其繁琐!
- 十字链表(专治有向图痛点 A):把有向图的“邻接表(管出边)”和“逆邻接表(管入边)”合二为一!一条有向弧只存 1 个结点,既能顺着查出度,又能顺着查入度。
- 邻接多重表(专治无向图痛点 B):让无向图的一条边只存 1 个边结点,同时挂在两个端点的链表上,删边只需改指针,无需找两处!
1. 邻接矩阵(Adjacency Matrix)—— 考察频率:⭐⭐⭐⭐⭐
一句话记忆
“稠密图首选,表示唯一,无向必对称,有向行出列入, 算路径条数”。
1.1 结构定义与代码骨架(408 算法大题高频)
用一个一维数组存顶点信息,一个二维数组 Edge[V][V] 存边的信息:
- 不带权图(无权图):有边记为
1,无边记为0(对角线Edge[i][i] = 0)。 - 带权图(网):有边记为权值 ,无边记为
∞(或0,对角线一般为0)。
408 真题标准结构体定义(MGraph)
#define MAXV 100 typedef struct { int numVertices, numEdges; // 顶点数 V 和边数 E char VerticesList[MAXV]; // 顶点表 int Edge[MAXV][MAXV]; // 邻接矩阵(边表) } MGraph;
1.2 核心性质与必考公式(选择题秒杀)
- 表示唯一性:只要顶点编号固定,图的邻接矩阵表示是唯一的!
- 空间复杂度:(只与顶点数 有关,与边数 无关!适合稠密图)。
- 无向图的邻接矩阵:
- 一定是一个对称矩阵(
Edge[i][j] == Edge[j][i])。因此在规模较大时,只需采用上/下三角压缩存储,空间可减半为 (主对角线全为 0 不用存)。 - 顶点 的度 = 第 行(或第 列)中非零元素的个数。
- 矩阵中非零元素的总个数 = (每条无向边贡献 2 个
1)。
- 一定是一个对称矩阵(
- 有向图的邻接矩阵:
- 不一定对称!“行出列入”(必背口诀):
- 第 行非零元个数 = 顶点 的出度 (从 发出的边)。
- 第 列非零元个数 = 顶点 的入度 (指向 的边)。
- 矩阵中非零元素的总个数 = 。
- 不一定对称!“行出列入”(必背口诀):
- 矩阵幂 的图论意义(408 真题大坑):
- 设邻接矩阵为 ,则 中的元素 表示从顶点 到顶点 长度为 (经过 条边)的路径总条数!
- 三角矩阵与拓扑排序的关系:
- 若有向图的邻接矩阵是上三角或下三角矩阵(主对角线为 0),则该图必为有向无环图(DAG),一定存在拓扑序列!
2. 邻接表(Adjacency List)—— 考察频率:⭐⭐⭐⭐⭐
一句话记忆
“稀疏图首选,表示不唯一,无向边存 2 份(2E),有向边存 1 份(E),有向求入度要遍历全表”。
2.1 结构长什么样?(顶点数组 + 边单链表)
- 顶点表结点(顺序数组):
[ data (顶点信息) | firstarc (指向第一条依附于该顶点的边) ] - 边表结点(单链表):
[ adjvex (邻接点下标) | weight (权值,可选) | nextarc (指向下一条边) ]
graph LR subgraph SG_V ["顶点表数组"] V0["0 | V0 | firstarc"] V1["1 | V1 | firstarc"] V2["2 | V2 | firstarc"] end V0 --> E01["adj:1 | next"] --> E02["adj:2 | NULL"] V1 --> E12["adj:2 | NULL"] V2 --> E20["adj:0 | NULL"]
408 真题标准结构体定义(ALGraph)
typedef struct ArcNode { // 边表结点 int adjvex; // 该弧所指向的顶点的位置(下标) struct ArcNode *nextarc; // 指向下一条弧的指针 // int info; // 网的边权值(可选) } ArcNode; typedef struct VNode { // 顶点表结点 char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 } VNode, AdjList[MAXV]; typedef struct { AdjList vertices; // 邻接表数组 int vexnum, arcnum; // 图的顶点数和弧数 } ALGraph;
2.2 核心性质与必考对比(无向 vs 有向)
| 对比维度 | 无向图的邻接表 | 有向图的邻接表(出边表) | 有向图的逆邻接表(入边表) |
|---|---|---|---|
| 边结点总数 | (一条边在两端各存一次) | ||
| 总空间复杂度 | |||
| 求某顶点的度 | 数第 个链表长度,时间 | 求流出的出度易(数第 个链表长度) 求流入的入度难(需遍历全部 个链表,时间 ) | 求入度易(数链表长度) 求出度难(需遍历全表) |
| 表示唯一性 | ❌ 不唯一(单链表中边结点的排列顺序任意,取决于建表插入顺序) | ❌ 不唯一 | ❌ 不唯一 |
3. 十字链表(Orthogonal List)—— 考察频率:⭐⭐⭐
408 第一铁律:十字链表 只能存【有向图】(或稀疏矩阵)!
考场上只要看到选项说“用十字链表存储无向图”,直接排掉! 核心目的:把有向图的邻接表和逆邻接表融合成一张表,解决“有向图邻接表求入度难”的痛点!
3.1 结点结构拆解(记住“顶点 3 域,弧结点 5 域”)
-
顶点结点(共 个,存于数组中)—— 3 个域:
[ data (顶点数据) | firstin (入边表头指针:指向以该点为弧头的第一条入边) | firstout (出边表头指针:指向以该点为弧尾的第一条出边) ] -
弧结点(共 个,每条有向边对应唯一 1 个结点)—— 5 个域:
[ tailvex (弧尾/起点下标) | headvex (弧头/终点下标) | hlink (指向弧头相同的下一条入边) | tlink (指向弧尾相同的下一条出边) | info (权值) ]
graph LR subgraph OL_V ["顶点结点:共 3 个域"] V["data | firstin:第一条入边 | firstout:第一条出边"] end subgraph OL_A ["弧结点:共 5 个域,表示有向边 tailvex 指向 headvex"] A["tailvex:起点 | headvex:终点 | hlink:同终点的下一条入边 | tlink:同起点的下一条出边 | info"] end
3.2 怎么操作?(考点秒杀)
- 求顶点 的出度:从
firstout出发,顺着弧结点的tlink(tail link,同起点) 一路往下数,时间复杂度 。 - 求顶点 的入度:从
firstin出发,顺着弧结点的hlink(head link,同终点) 一路往下数,时间复杂度 。 - 空间复杂度: 个顶点结点 + 个弧结点 = 。
- 唯一性:❌ 不唯一。
4. 邻接多重表(Adjacency Multilist)—— 考察频率:⭐⭐⭐
408 第二铁律:邻接多重表 只能存【无向图】!
考场上只要看到选项说“用邻接多重表存储有向图”,直接排掉! 核心目的:解决无向图在普通邻接表中“一条边存 2 个结点(空间翻倍)且删除一条边需要找两个链表结点”的痛点!在邻接多重表中,一条无向边只用 1 个边结点!
4.1 结点结构拆解(记住“顶点 2 域,边结点 6 域”)
-
顶点结点(共 个,存于数组中)—— 2 个域:
[ data (顶点数据) | firstedge (指向第一条依附于该顶点的边) ] -
边结点(共 个,每条无向边对应唯一 1 个结点!)—— 6 个域(不计权值和标记则为 4 个核心域):
[ mark (访问标记) | ivex (边的一个端点 i) | ilink (指向依附于顶点 ivex 的下一条边) | jvex (边的另一个端点 j) | jlink (指向依附于顶点 jvex 的下一条边) | info (权值) ]
graph LR subgraph AML_V ["顶点结点:共 2 个域"] V["data | firstedge:第一条依附边"] end subgraph AML_E ["边结点:共 6 个域,表示无向边 ivex 连接 jvex"] E["mark | ivex:端点i | ilink:连着i的下一条边 | jvex:端点j | jlink:连着j的下一条边 | info"] end
4.2 邻接表 vs 邻接多重表(无向图终极对比)
| 对比项 | 无向图的邻接表 | 无向图的邻接多重表 |
|---|---|---|
| 边结点数量 | 个(每条边存两份) | 个(每条边只存一份!) |
| 每个边结点的指针域数 | 1 个(nextarc) | 2 个(ilink 和 jlink) |
| 删除一条边 | 麻烦:必须分别在 的链表和 的链表中找到两个结点并删除 | 极方便:只需找到这唯一的边结点,修改 ilink 和 jlink 前驱指针即可 |
| 求顶点 的所有相连边 | 顺着 nextarc 一直走 | 在边结点中看哪一端是 (若 ivex == i 则顺着 ilink 走;若 jvex == i 则顺着 jlink 走) |
📋 5. 图的四大存储结构全景速查表(考前必背)
| 存储结构 | 适用图类型 | 顶点结点数 | 边/弧结点数 | 空间复杂度 | 判两点是否有边 | 找某点所有邻接点 | 求入度/出度(或度) | 表示唯一? |
|---|---|---|---|---|---|---|---|---|
| 邻接矩阵 | 有向 / 无向 (稠密图) | 无(二维数组 ) | 行和=出度,列和=入度 时间均为 | ✅ 唯一 | ||||
| 邻接表 | 无向稀疏图 | 求度: | ❌ 不唯一 | |||||
| 邻接表 | 有向稀疏图 | 求出度: 求入度:(慢!) | ❌ 不唯一 | |||||
| 十字链表 | 仅限有向稀疏图 | 求出度、入度均极快 | ❌ 不唯一 | |||||
| 邻接多重表 | 仅限无向稀疏图 | 求度快,删边/标记边极方便 | ❌ 不唯一 |
📝 6. 历年真题与经典好题精选(实战演练·破局版)
真题 1(四大存储结构适用性辨析 · 408 高频母题)
题目:下列关于图的存储结构的叙述中,错误的是( )。 A. 用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中顶点数有关,而与边的条数无关 B. 邻接表只能用于有向图的存储,邻接多重表只能用于无向图的存储 C. 若一个有向图的邻接矩阵对角线以下元素均为 0,则该图的拓扑序列必定存在 D. 十字链表既是稀疏矩阵的一种链式存储结构,也是有向图的一种链式存储结构
🧠 破局思路(题眼 + 步骤)
- A 正确:邻接矩阵固定是 的二维数组,空间复杂度 ,与边数 无关。
- B 错误:邻接表既能存有向图,也能存无向图!真正有排他限制的是:十字链表只能存有向图,邻接多重表只能存无向图!
- C 正确:对角线以下全为 0 即上三角矩阵,边只能从小编号指向大编号,必无环,故必存在拓扑序列。
- D 正确:十字链表在“稀疏矩阵”和“有向图”中都是核心链式结构。 结论:选 B。
真题 2(边结点个数与指针域数量计算 · 经典必刷)
题目:设无向图 有 个顶点和 条边。若采用邻接表存储,则边表结点的总数为( ① ),所有边表结点中指针域的总数为( ② );若改用邻接多重表存储,则边结点的总数为( ③ ),所有边结点中指向边的指针域总数为( ④ )。
🧠 破局思路(题眼 + 步骤) 题眼:区分无向图在“邻接表”和“邻接多重表”中的结点数与指针数!
- 无向图邻接表:一条边存两份 边表结点总数 ① = ;每个边表结点只有 1 个
nextarc指针域 指针域总数 ② = 。- 无向图邻接多重表:一条边只存 1 个结点 边结点总数 ③ = ;但每个边结点里有
ilink和jlink2 个指向下一条边的指针域 指针域总数 ④ = ! 💡 重要发现:你会发现,邻接多重表之所以比邻接表省空间,是因为它少存了 份重复的顶点下标(adjvex)和边权值(info),而指针域的总个数其实都是 ! 结论:① ,② ,③ ,④ 。
真题 3(2021 年 408 算法统考大题背景 · 邻接矩阵与度计算)
题目:已知无向连通图 由顶点集 和边集 组成,。当 中度为奇数的顶点个数为不大于 2 的偶数时, 存在包含所有边且长度为 的路径(称为 EL 路径 / 欧拉路径)。设图 采用邻接矩阵存储,类型定义如下:
typedef struct { int numVertices, numEdges; char VerticesList[MAXV]; int Edge[MAXV][MAXV]; } MGraph;请设计算法
int IsExistEL(MGraph G),判断 是否存在 EL 路径,存在返回 1,否则返回 0,并说明时间复杂度和空间复杂度。🧠 破局思路 + 满分代码模板 破局思路:无向图在邻接矩阵中,顶点 的度就是第 行非零元素的个数!只需双重循环统计每一行的非零元个数
degree,若degree % 2 != 0则计数器count++。最后判断count == 0 || count == 2即可!int IsExistEL(MGraph G) { int count = 0; // 记录度为奇数的顶点个数 for (int i = 0; i < G.numVertices; i++) { int degree = 0; for (int j = 0; j < G.numVertices; j++) { if (G.Edge[i][j] != 0) degree++; // 无向图第 i 行非零元个数即为顶点 i 的度 } if (degree % 2 != 0) count++; // 奇数度顶点统计 } if (count == 0 || count == 2) return 1; // 奇数度顶点数为 0 或 2 时存在 EL 路径 else return 0; }复杂度:需要遍历整个二维邻接矩阵,时间复杂度 ,空间复杂度 。