408

数据结构

图的存储（邻接矩阵/邻接表/邻接多重表/十字链表）

---

一、定位信息

• 圈层：核心层（大纲考点）
• 前置知识：图的基本概念（顶点、边、有向/无向、度）、线性表（链表）。
• 知识网络定位：图的存储是图遍历（DS-05-03）及其他图算法的实现基础，选择合适的存储结构直接影响算法的时间和空间效率。
• 考点热度：H级（高频重点） — 邻接矩阵和邻接表是408必考内容，近5年真题中出现 ≥4 次，常以选择题和代码填空题形式出现。

---

二、知识点讲解

2.1 邻接矩阵（Adjacency Matrix）

用一个 $n \times n$ 的二维数组 $A$ 存储图。对于图 $G = (V, E)$，$|V| = n$：

$$A[i][j] = \begin{cases} 1, & \text{若} (v_i, v_j) \in E \text{ 或 } \langle v_i, v_j \rangle \in E \ 0, & \text{否则} \end{cases}$$

对于网（带权图）：

$$A[i][j] = \begin{cases} w_{ij}, & \text{若} (v_i, v_j) \in E \text{ 或 } \langle v_i, v_j \rangle \in E \ \infty \text{ 或 } 0, & \text{否则（} \infty \text{表示无边，对角线为0）} \end{cases}$$

特点：

• 无向图的邻接矩阵是对称矩阵，只需存储上三角或下三角。
• 空间复杂度：$O(n^2)$，与边数无关。
• 适合稠密图。

2.2 邻接表（Adjacency List）

为每个顶点建立一个单链表，链表中存储该顶点的所有邻接顶点。

结构：

• 顶点表：数组 $V[n]$，每个元素包含顶点数据和指向第一个邻接点的指针。
• 边表：每个顶点对应一个链表，链表节点包含邻接顶点下标、权值（网）和指向下一个邻接点的指针。

特点：

• 无向图：每条边存储两次。顶点 $v_i$ 的度 = 边表 $i$ 的长度。
• 有向图：每条弧存储一次。顶点 $v_i$ 的出度 = 边表 $i$ 的长度；入度需遍历所有边表。
• 空间复杂度：$O(n + e)$。
• 适合稀疏图。

2.3 十字链表（Orthogonal List）

适用：有向图/有向网的存储。

将邻接表和逆邻接表合二为一。每个弧节点包含：

• tailvex：弧尾下标
• headvex：弧头下标
• hlink：指向弧头相同的下一条弧
• tlink：指向弧尾相同的下一条弧
• info：弧的信息（权值等）

每个顶点节点包含：

• data：顶点数据
• firstin：指向以该顶点为弧头的第一条弧
• firstout：指向以该顶点为弧尾的第一条弧

特点：既能快速求出度（沿 firstout 链），也能快速求入度（沿 firstin 链）。弧节点数 = $e$。

2.4 邻接多重表（Adjacency Multilist）

适用：无向图的存储，特别适合需要对边做标记操作的场景。

每条边用一个边节点表示，包含：

• mark：标志域（标记是否被访问）
• ivex、jvex：边的两个顶点下标
• ilink：指向依附于 $ivex$ 的下一条边
• jlink：指向依附于 $jvex$ 的下一条边
• info：边的信息

每个顶点节点包含 data 和 firstedge（指向依附于该顶点的第一条边）。

特点：每条边只存储一次（不像邻接表存两次），方便边的删除等操作。

---

三、记忆与理解辅助

技巧 1：存储结构选择口诀

• "稠密矩阵稀疏表，有向十字无向多"
• 稠密图 → 邻接矩阵；稀疏图 → 邻接表
• 有向图需快速查入度 → 十字链表；无向图需操作边 → 邻接多重表

技巧 2：空间复杂度对比

存储结构	空间复杂度	适用场景	度的求法
邻接矩阵	$O(n^2)$	稠密图	无向：第 $i$ 行（或列）之和；有向：行和为出度，列和为入度
邻接表	$O(n+e)$	稀疏图	无向：边表长度 = 度；有向：边表长度 = 出度，入度需遍历
十字链表	$O(n+e)$	有向图（需查入度）	firstout 链长 = 出度，firstin 链长 = 入度
邻接多重表	$O(n+e)$	无向图（需操作边）	遍历 ilink/jlink

技巧 3：邻接矩阵 vs 邻接表深层对比

对比维度	邻接矩阵	邻接表
空间	$O(n^2)$	$O(n+e)$
判断边是否存在	$O(1)$	$O(\text{度})$
求所有邻接点	$O(n)$	$O(\text{度})$
增加/删除边	$O(1)$	$O(1)$（头插法）
适合图的类型	稠密图	稀疏图
唯一性	唯一	不唯一（链表顺序可变）

技巧 4：邻接矩阵的幂

• $A^k[i][j]$ 表示从 $v_i$ 到 $v_j$ 长度为 $k$ 的路径数目。这个性质在某些题目中非常有用。

---

四、例题与精解

例题 1（基础巩固）

题目：对下图给出的无向图，写出其邻接矩阵和邻接表表示。

【图示说明】无向图有 5 个顶点 $v_0, v_1, v_2, v_3, v_4$，边集为 $\{(v_0,v_1), (v_0,v_3), (v_1,v_2), (v_1,v_4), (v_2,v_4), (v_3,v_4)\}$。

命题意图：考查邻接矩阵和邻接表的基本构造能力。

审题分析：

• 已知：5 个顶点、6 条边的无向图。
• 求解：邻接矩阵和邻接表。

解题思路：逐一检查每对顶点是否有边，填写矩阵；对每个顶点，将其所有邻接点串成链表。

完整步骤：

邻接矩阵（$5 \times 5$，对称矩阵）：

	$v_0$	$v_1$	$v_2$	$v_3$	$v_4$
$v_0$	0	1	0	1	0
$v_1$	1	0	1	0	1
$v_2$	0	1	0	0	1
$v_3$	1	0	0	0	1
$v_4$	0	1	1	1	0

邻接表：

• $v_0 \to v_3 \to v_1$
• $v_1 \to v_4 \to v_2 \to v_0$
• $v_2 \to v_4 \to v_1$
• $v_3 \to v_4 \to v_0$
• $v_4 \to v_3 \to v_2 \to v_1$

（注：邻接表不唯一，取决于插入顺序。）

方法反思：无向图邻接矩阵必对称；邻接表中每条边出现两次。

---

例题 2（中等提升）

题目：设图 $G$ 有 $n$ 个顶点、$e$ 条边，采用邻接表存储。求以下操作的时间复杂度：

1. 判断顶点 $v_i$ 和 $v_j$ 之间是否有边。
2. 求顶点 $v_i$ 的度。
3. 遍历图中所有边。

命题意图：考查对邻接表存储结构的时间复杂度分析能力。

审题分析：

• 已知：邻接表存储的图，$n$ 个顶点，$e$ 条边。
• 求解：三种操作的时间复杂度。

解题思路：分析邻接表的结构特点，针对每种操作确定需要遍历的范围。

完整步骤：

1. 判断 $v_i$ 和 $v_j$ 是否有边：

   • 需要在 $v_i$ 的边表中查找是否存在 $v_j$。
   • 时间复杂度：$O(\text{deg}(v_i))$，最坏 $O(n)$。
   • （对比邻接矩阵只需 $O(1)$：直接查 $A[i][j]$。）

2. 求 $v_i$ 的度：

   • 无向图：遍历 $v_i$ 的边表，长度即为度。时间复杂度：$O(\text{deg}(v_i))$。
   • 有向图：边表长度 = 出度，求入度需遍历所有顶点的边表。时间复杂度：出度 $O(\text{deg}(v_i))$，入度 $O(e)$。

3. 遍历所有边：

   • 遍历所有顶点的边表。无向图每条边出现两次，总长度 $2e$。
   • 时间复杂度：$O(n + e)$。

方法反思：邻接表的核心优势在于"只花与实际边数成正比的空间和时间"，这在稀疏图中优势明显。变式：同样的问题用邻接矩阵做，对比时间复杂度。

---

五、考情分析

• 考查频次：近 5 年真题中，邻接矩阵和邻接表相关题目出现 ≥4 次，十字链表和邻接多重表偶有涉及（约 1–2 次）。
• 常见题型：选择题（存储结构对比、空间复杂度分析）、综合题（结合遍历算法的代码填空）。
• 分值占比：约 2–4 分（选择题）或作为综合题的一部分（4–6 分）。
• 命题趋势：邻接矩阵和邻接表是高频考点，十字链表和邻接多重表的考查频率较低，但仍需掌握原理。近年来更注重对存储结构选择依据的考查。
• 基于大纲与命题规律推测

---

六、易错点提醒

1. 错误表现：有向图邻接矩阵中，将行和与列和的含义搞反。 错误原因：矩阵 $A[i][j]=1$ 表示从 $v_i$ 到 $v_j$ 有弧，所以第 $i$ 行之和 = $v_i$ 的出度，第 $j$ 列之和 = $v_j$ 的入度。 正确理解：行→出度，列→入度。口诀："行出列入"。

2. 错误表现：在邻接表中，有向图只看到出度边表，就认为无法求入度。 错误原因：标准邻接表确实只能直接看出度，求入度需要遍历所有顶点的边表，统计指向目标顶点的弧数。这是邻接表的缺点之一，也是十字链表出现的原因。 正确理解：邻接表求入度效率低 $O(e)$；若需频繁求入度，应改用十字链表。

3. 错误表现：无向图邻接表中，认为边节点数等于 $e$。 错误原因：无向图每条边在两个顶点的边表中各出现一次，所以边节点总数为 $2e$。 正确理解：无向图邻接表边节点数 $= 2e$；有向图邻接表边节点数 $= e$。

4. 错误表现：混淆邻接多重表和邻接表的结构。 错误原因：邻接多重表是为无向图设计的，每条边只存储一次（一个边节点），通过 ilink 和 jlink 分别链接到两个顶点的边链中。而邻接表中每条边存两次。 正确理解：邻接多重表 = 无向图的"优化版邻接表"，减少冗余存储。

---

七、来源标注

• 依据 2026 考研统考大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据大学本科经典教材共识