408 高频考点精讲:邻接矩阵(Adjacency Matrix Representation and Applications)¶
模块归属:数据结构 · 图结构
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:3 次(2016~2025 年:2021#41、2023#41、2024#41)
- 历年总考查频次:6 次(含选择题 2009#7、2014#7、2015#6 等)
- 出题形式:单项选择题、算法设计综合题(近四年中 3 次作为第 41 题大题核心存储结构,分值均为 13 分)
- 命题特点:
- 大题命题载体集中:近年 408 数据结构算法大题高度青睐邻接矩阵。连续考查度数统计、欧拉路径判定、有向图拓扑序列唯一性判定等算法,考查以邻接矩阵作为底层图结构的算法设计能力。
- 行列属性辨析清晰:严格考查有向图邻接矩阵中“行对应出边、列对应入边”的代数映射关系,以及无向图邻接矩阵的主对角线对称性。
- 离散数学代数性质渗透:在选择题中常考查邻接矩阵的幂 \(A^k\)$ \text{与图中长度为} $\(k\) 的路径数目之间的图论代数定理推导。
二、 具体考察内容¶
1. 邻接矩阵的数据结构定义及规范¶
邻接矩阵(Adjacency Matrix)是借助二维数组表达图拓扑结构的基本方式。设图 \(G = (V, E)\)$ \text{包含} $\(n\)$ \text{个顶点,其顶点集合为} $\(V = \{v_0, v_1, \dots, v_{n-1}\}\)$ \text{,边集合为} $\(E\)$ \text{。图的邻接矩阵是一个} $\(n \times n\)$ \text{的二阶矩阵} $\(A\)。
(1) 无权图的邻接矩阵¶
对于不带权值的简单无向图或有向图,矩阵元素定义为: $$ \text{A[i][j] = \begin{cases} 1, & \text{若 } (v_i, v_j) \in E \text{ 或 } \langle v_i, v_j \rangle \in E \ 0, & \text{若 } (v_i, v_j) \notin E \text{ 且 } \langle v_i, v_j \rangle \notin E \end{cases}} $$
(2) 带权图(网)的邻接矩阵¶
对于包含边权值的网络(Net),矩阵元素存储对应的边权值 \(w_{ij}\)$ \text{。不存在直连边的顶点对之间,通常使用宏定义的无穷大} $\(\infty\)(计算机中取最大整数 0x3f3f3f3f 或 INT_MAX)表示;自身到自身的对角线元素一般约定为 0:
$$ \text{A[i][j] = \begin{cases} w_{ij}, & \text{若 } i \ne j \text{ 且存在边} \ 0, & \text{若 } i = j \ \infty, & \text{若 } i \ne j \text{ 且不存在边} \end{cases}} $$
(3) 408 统考标准 C 语言定义结构体¶
#define MAXV 100 // 最大顶点数定义
#define INF 0x3f3f3f3f // 表示无穷大(带权网中无边情况)
typedef struct {
int numVertices; // 图的当前顶点数
int numEdges; // 图的当前边数
char VerticesList[MAXV]; // 顶点表(存储顶点信息)
int Edge[MAXV][MAXV]; // 邻接矩阵(无权图存 0/1,带权网存权值/INF)
} MGraph;
2. 邻接矩阵的核心定理及数学推导¶
定理一:无向图邻接矩阵的对称性与压缩存储¶
- 定理表述:无向图的邻接矩阵必为主对角线对称矩阵,即 \(A = A^T\)$ \text{,对于任意} $\(i, j \in [0, n-1]\)$ \text{,恒有} $\(A[i][j] = A[j][i]\)。
- 压缩存储推导: 由于 \(A[i][j] = A[j][i]\)$ \text{,可仅将下三角部分(包含主对角线)压缩存入一维数组} $\(B\) 中。 下三角区域中包含的元素总数为: $\(S = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\)$ 采用行优先顺序存放时,矩阵元素 \(A[i][j]\)$ \text{(设} $\(i \ge j\)$ \text{)前面完整的行共有} $\(i\)$ \text{行(行号} $\(0, 1, \dots, i-1\)),其包含的元素总数为: $\(\sum_{r=0}^{i-1} (r+1) = \frac{i(i+1)}{2}\)$ 在第 \(i\)$ \text{行中,元素} $\(A[i][j]\)$ \text{是当前行第} $\(j\)$ \text{个元素(下标从 0 计数)。因此,元素} $\(A[i][j]\)$ \text{对应一维数组} $\(B\)$ \text{中的下标} $\(k\) 为: $\(k = \frac{i(i+1)}{2} + j \quad (i \ge j)\)$ 当访问上三角元素 \(A[i][j]\)(\(i < j\)$ \text{)时,由对称性直接映射为访问} $\(A[j][i]\): $\(k = \frac{j(j+1)}{2} + i \quad (i < j)\)$
定理二:顶点度数计算法则(行出列入定理)¶
- 无向图度数: 无向图中,顶点 \(v_i\)$ \text{的度} $\(\deg(v_i)\)$ \text{等于邻接矩阵第} $\(i\)$ \text{行(或第} $\(i\) 列)非零元素的总个数: $\(\deg(v_i) = \sum_{j=0}^{n-1} A[i][j] = \sum_{j=0}^{n-1} A[j][i]\)$ 全矩阵非零元素总和等于图总边数的 2 倍: $\(\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} A[i][j] = \sum_{i=0}^{n-1} \deg(v_i) = 2|E|\)$
- 有向图出度与入度: 有向图中,边由弧尾指向弧头,即 \(A[i][j] = 1\)$ \text{表示存在弧} $\(\langle v_i, v_j \rangle\)。
- 出度(Out-degree):顶点 \(v_i\)$ \text{的出度等于第} $\(i\) 行非零元素之和(行出): $\(\text{OD}(v_i) = \sum_{j=0}^{n-1} A[i][j]\)$
- 入度(In-degree):顶点 \(v_j\)$ \text{的入度等于第} $\(j\) 列非零元素之和(列入): $\(\text{ID}(v_j) = \sum_{i=0}^{n-1} A[i][j]\)$
- 顶点总度数:\(\deg(v_i) = \text{OD}(v_i) + \text{ID}(v_i)\)。
- 边数关系:全矩阵非零元素总和恰好等于有向边数: $\(\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} A[i][j] = \sum_{i=0}^{n-1} \text{OD}(v_i) = \sum_{j=0}^{n-1} \text{ID}(v_j) = |E|\)$
定理三:邻接矩阵的幂运算代数意义(路径计数定理)¶
- 定理表述: 设 \(A\)$ \text{为图} $\(G\)$ \text{的} $\(0-1\)$ \text{邻接矩阵,} $\(A^m\)$ \text{为} $\(A\)$ \text{的} $\(m\)$ \text{次幂(} $\(m \ge 1\)$ \text{),则} $\(A^m\)$ \text{的第} $\(i\)$ \text{行第} $\(j\)$ \text{列元素} $\((A^m)_{ij}\)$ \text{等于从顶点} $\(v_i\)$ \text{到顶点} $\(v_j\)$ \text{长度为} $\(m\) 的路径(Walk,途径)数目。
- 严格数学归纳法证明:
- 基础步(\(m = 1\)): 当 \(m = 1\)$ \text{时,} $\((A^1)_{ij} = A[i][j]\)$ \text{。根据邻接矩阵定义,若存在边则为 1,不存在则为 0。长度为 1 的路径即为图的一条单边。此时} $\((A^1)_{ij}\)$ \text{恰好等于从} $\(v_i\)$ \text{到} $\(v_j\) 长度为 1 的路径数,基础步成立。
- 归纳假设: 假设当 \(m = k\)(\(k \ge 1\)$ \text{)时定理成立,即矩阵元素} $\((A^k)_{il}\)$ \text{表示从顶点} $\(v_i\)$ \text{到顶点} $\(v_l\)$ \text{长度为} $\(k\) 的路径总数。
- 归纳步(\(m = k + 1\)):
考查 \(A^{k+1} = A^k \cdot A\)$ \text{。根据矩阵乘法运算法则,其第} $\(i\)$ \text{行第} $\(j\) 列元素展开为:
$\((A^{k+1})_{ij} = \sum_{l=0}^{n-1} (A^k)_{il} \cdot A[l][j]\)$
在图拓扑中,任意一条从 \(v_i\)$ \text{到} $\(v_j\)$ \text{且长度为} $\(k+1\)$ \text{的路径,均可唯一拆解为:先由} $\(v_i\)$ \text{经过一条长度为} $\(k\)$ \text{的路径到达中间顶点} $\(v_l\)$ \text{,再由} $\(v_l\)$ \text{经过一条长度为 1 的边到达目标终点} $\(v_j\)。
由乘法原理,经过特定中间顶点 \(v_l\)$ \text{的长度为} $\(k+1\)$ \text{的路径数为} $\((A^k)_{il} \times A[l][j]\):
- 若 \(A[l][j] = 0\)$ \text{,表示不存在连边} $\(\langle v_l, v_j \rangle\),乘积为 0;
- 若 \(A[l][j] = 1\)$ \text{,则该路径数等于从} $\(v_i\)$ \text{到} $\(v_l\)$ \text{长度为} $\(k\)$ \text{的路径总数} $\((A^k)_{il}\)。 根据加法原理,中间顶点 \(v_l\)$ \text{的取值互斥,遍历所有顶点集合} $\(l \in [0, n-1]\)$ \text{进行求和,所求和式恰好等于从} $\(v_i\)$ \text{到} $\(v_j\)$ \text{长度为} $\(k+1\) 的全部路径数目。 因此对 \(m = k + 1\) 定理依然成立。
- 结论: 由数学归纳法可知,对任意正整数 \(m \ge 1\),\((A^m)_{ij}\)$ \text{恒等于从} $\(v_i\)$ \text{到} $\(v_j\)$ \text{长度为} $\(m\) 的路径数目。
3. 邻接矩阵同邻接表特性对比¶
| 评测维度 | 邻接矩阵(Adjacency Matrix) | 邻接表(Adjacency List) |
|---|---|---|
| 空间复杂度 | 恒为 \(O(\|V\|^2)\)$ \text{,与边数} $\(\|E\|\)$ \text{无关 | } $\(O(\|V\| + \|E\|)\),空间利用率随边数线性变化 |
| 适用图类型 | 稠密图(Dense Graph,\(\|E\| \approx \|V\|^2\)$ \text{) | 稀疏图(Sparse Graph,} $\(\|E\| \ll \|V\|^2\)) |
| 判定是否存在边 \((u, v)\) | \(O(1)\)$ \text{,直接索引访问} $\(A[u][v]\) | \(O(\deg(u))\)$ \text{,需线性遍历顶点} $\(u\) 的出边链表 |
| 寻找某顶点 \(u\)$ \text{的全部邻接点 | } $\(O(\|V\|)\)$ \text{,必须完整扫描整行向量 | } $\(O(\deg(u))\),仅需遍历单链表结点 |
| 求无向图顶点 \(u\)$ \text{的度 | } $\(O(\|V\|)\)$ \text{,统计第} $\(u\)$ \text{行非零元素数 | } $\(O(\deg(u))\),直接统计该单链表长度 |
| 求有向图顶点 \(u\)$ \text{的出度 | } $\(O(\|V\|)\)$ \text{,统计第} $\(u\)$ \text{行非零元素数 | } $\(O(\text{OD}(u))\),直接统计该单链表长度 |
| 求有向图顶点 \(u\)$ \text{的入度 | } $\(O(\|V\|)\)$ \text{,统计第} $\(u\)$ \text{列非零元素数 | } $\(O(\|V\| + \|E\|)\),需遍历全图所有结点的边表 |
| 插入/删除一条边 | \(O(1)\)$ \text{,直接修改矩阵单元数值 | 插入} $\(O(1)\)$ \text{,删除需} $\(O(\deg(u))\) 寻址节点 |
| 表示唯一性 | 唯一(给定顶点标号顺序后形态唯一确定) | 不唯一(链表中结点的插入链接先后次序不影响图结构) |
4. 408 统考算法大题四大核心矩阵操作范式¶
在 408 统考真题中,基于邻接矩阵的算法考查通常依托以下四类矩阵操作模板:
范式一:行和与列和同步遍历范式(度数统计模式)¶
用于高效统计顶点的出度、入度或无向图的度数。利用单层循环内同时递增行索引与列索引,降低代码冗余:
// 统计顶点 i 的出度与入度
int outDegree = 0, inDegree = 0;
for (int j = 0; j < G.numVertices; j++) {
if (G.Edge[i][j] != 0) outDegree++; // 行累加求出度
if (G.Edge[j][i] != 0) inDegree++; // 列累加求入度
}
范式二:入度向量预处理与动态消边范式(拓扑排序模式)¶
在邻接矩阵中进行拓扑排序时,由于直接查矩阵列入度每次需 \(O(n)\),通常先预处理全局入度数组 inDegree[n],删除顶点时仅更新后继顶点的入度值:
int inDegree[MAXV] = {0};
// 1. 列扫描统计所有顶点入度
for (int j = 0; j < G.numVertices; j++) {
for (int i = 0; i < G.numVertices; i++) {
if (G.Edge[i][j] != 0) inDegree[j]++;
}
}
// 2. 顶点消边操作(顶点 u 出栈后更新其后继)
for (int v = 0; v < G.numVertices; v++) {
if (G.Edge[u][v] != 0) {
inDegree[v]--; // 动态消去边 <u, v>
}
}
范式三:基于邻接矩阵的广度优先遍历(BFS 模板)¶
void BFS_Matrix(MGraph G, int start, int visited[]) {
int queue[MAXV], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int u = queue[front++];
// 扫描邻接矩阵第 u 行探寻相邻顶点
for (int v = 0; v < G.numVertices; v++) {
if (G.Edge[u][v] != 0 && !visited[v]) {
visited[v] = 1;
queue[rear++] = v;
}
}
}
}
范式四:基于邻接矩阵的深度优先遍历(DFS 模板)¶
void DFS_Matrix(MGraph G, int u, int visited[]) {
visited[u] = 1;
// 线性遍历行向量
for (int v = 0; v < G.numVertices; v++) {
if (G.Edge[u][v] != 0 && !visited[v]) {
DFS_Matrix(G, v, visited);
}
}
}
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 统考第 41 题 · 拓扑序列唯一性判定¶
题目
有向图 \(G\) 采用邻接矩阵存储,类型定义如下:
typedef struct {
int numVertices, numEdges; // 图的顶点数和有向边数
char verticesList[MAXV]; // 顶点表
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int uniquely(MGraph G)。判定 \(G\) 是否存在唯一的拓扑序列,若是则返回 1,否则返回 0。要求:
1. 给出算法的基本设计思想;
2. 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释;
3. 说明算法的时间复杂度。
【解析】¶
1. 算法设计思想¶
拓扑排序的推进过程依赖于入度为 0 的顶点。在图拓扑排序的任意一步中,若当前待处理图中入度为 0 的顶点个数: - 大于 1 个:说明存在多个相互独立的起始顶点,可任意选其一排入序列,后续序列形态必然分叉,导致拓扑序列不唯一,算法直接返回 0; - 等于 0 个(且处理的顶点总数未达到 \(n\)):说明剩余子图中存在有向环路,无法形成合法的拓扑序列,返回 0; - 严格等于 1 个:此时输出选择唯一确定,将其移出图结构并将其邻接后继顶点的入度减 1,继续考察下一步。
因此,有向图存在唯一拓扑序列的充要条件为:在拓扑排序的每一步选择中,全图中入度为 0 的待处理顶点有且仅有 1 个,且该操作成功重复推进 \(n\) 轮。
算法具体步骤:
- 步骤 1:构建辅助数组 inDegree[n]。通过双重循环按列扫描邻接矩阵,累加计算所有顶点的初始入度。
- 步骤 2:启动一个执行 \(n\) 次的循环,每轮在线性扫描 inDegree 数组时统计入度为 0 的顶点数目。
- 步骤 3:若计数不为 1,直接返回 0;若计数恰好为 1,记录该唯一顶点的编号 \(u\)。
- 步骤 4:将该顶点入度标记为已访问(如置为 \(-1\)$ \text{),并扫描第} $\(u\)$ \text{行的所有出边} $\(G.Edge[u][v]\)$ \text{,将其后继顶点} $\(v\) 的入度减 1。
- 步骤 5:若成功执行完 \(n\) 轮循环,说明存在且仅存在唯一的拓扑序列,返回 1。
2. C/C++ 算法实现¶
int uniquely(MGraph G) {
int n = G.numVertices;
int inDegree[MAXV];
// 1. 初始化入度数组并统计各顶点的初始入度
for (int j = 0; j < n; j++) {
inDegree[j] = 0;
for (int i = 0; i < n; i++) {
if (G.Edge[i][j] != 0) {
inDegree[j]++;
}
}
}
// 2. 依次确定拓扑序列中的每一个顶点,共循环 n 轮
for (int step = 0; step < n; step++) {
int zeroCount = 0; // 记录当前入度为 0 的顶点数目
int u = -1; // 记录唯一入度为 0 的顶点索引
// 扫描入度数组寻找入度为 0 的顶点
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
zeroCount++;
u = i;
}
}
// 充要条件判定:若入度为 0 的顶点数不等于 1,则拓扑序列不唯一或存在环
if (zeroCount != 1) {
return 0;
}
// 3. 将选中的唯一顶点标记为已处理(避免后续重复选择)
inDegree[u] = -1;
// 4. 遍历顶点 u 的出边,消去其对后继顶点的入度贡献
for (int v = 0; v < n; v++) {
if (G.Edge[u][v] != 0) {
inDegree[v]--;
}
}
}
// 成功推进 n 步,说明存在唯一的拓扑序列
return 1;
}
3. 复杂度分析¶
- 时间复杂度:
- 初始统计入度遍历全矩阵,耗时 \(O(n^2)\);
- 外层循环执行 \(n\)$ \text{轮,每轮扫描入度数组耗时} $\(O(n)\)$ \text{,消边遍历行向量耗时} $\(O(n)\)$ \text{,单轮总耗时为} $\(O(n)\)$ \text{,故循环部分总耗时为} $\(n \times O(n) = O(n^2)\);
- 综上,算法总时间复杂度为 \(O(n^2)\)。
- 空间复杂度:
算法仅引入了大小为 \(n\)$ \text{的一维整型辅助数组
inDegree,辅助空间复杂度为} $\(O(n)\)。
【真题 2】2023 年 408 统考第 41 题 · K 顶点输出与计数¶
题目
已知有向图 \(G\) 采用邻接矩阵存储,类型定义如下:
typedef struct {
int numVertices, numEdges;
char VerticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
设计算法
int printVertices(MGraph G),对给定任意非空有向图 \(G\)$ \text{,输出} $\(G\) 中所有 K 顶点,并返回 K 顶点的个数。要求:
1. 给出算法的设计思想;
2. 根据算法思想,写出 C/C++ 描述并注释;
3. 说明算法的时间复杂度。
【解析】¶
1. 算法设计思想¶
在有向图的邻接矩阵中: - 任意顶点 \(i\)$ \text{的出度(Out-degree)等于其对应的行向量中所有非零元素之和:} $\(\text{outdegree}(i) = \sum_{j=0}^{n-1} Edge[i][j]\); - 任意顶点 \(i\)$ \text{的入度(In-degree)等于其对应的列向量中所有非零元素之和:} $\(\text{indegree}(i) = \sum_{j=0}^{n-1} Edge[j][i]\)。
算法设计:
初始化计数器 count = 0。遍历图中的每一个顶点 \(i \in [0, n-1]\)$ \text{,在内层循环中利用单个循环变量} $\(j\)$ \text{同时完成第} $\(i\)$ \text{行元素(出边)累加与第} $\(i\) 列元素(入边)累加。当单顶点的出度大于入度时,输出对应顶点信息 VerticesList[i],并将计数器累加 1。遍历完毕后返回 count。
2. C/C++ 算法实现¶
int printVertices(MGraph G) {
int count = 0; // 记录 K 顶点的总个数
int n = G.numVertices;
// 遍历图中的每一个顶点
for (int i = 0; i < n; i++) {
int outdegree = 0; // 记录顶点 i 的出度
int indegree = 0; // 记录顶点 i 的入度
// 同步扫描第 i 行与第 i 列
for (int j = 0; j < n; j++) {
if (G.Edge[i][j] != 0) {
outdegree++; // 统计出度(第 i 行)
}
if (G.Edge[j][i] != 0) {
indegree++; // 统计入度(第 i 列)
}
}
// 判断出度是否大于入度
if (outdegree > indegree) {
printf("%c ", G.VerticesList[i]); // 输出 K 顶点
count++; // 计数加 1
}
}
return count; // 返回 K 顶点个数
}
3. 复杂度分析¶
- 时间复杂度: 外层循环总共遍历 \(n\)$ \text{个顶点,内层单循环执行} $\(n\)$ \text{次同步累加,总的矩阵访问次数为} $\(2n^2\)$ \text{,因此算法的时间复杂度为} $\(O(n^2)\)。
- 空间复杂度: 算法只使用了若干个局部整型标量变量,未使用任何额外的动态数组或辅助容器,因此辅助空间复杂度为 \(O(1)\)。
【真题 3】2021 年 408 统考第 41 题 · 欧拉路径存在性判定¶
题目
已知无向连通图 \(G\)$ \text{由顶点集} $\(V\)$ \text{和边集} $\(E\)$ \text{组成,} $\(|E| > 0\)$ \text{。当} $\(G\)$ \text{中度为奇数的顶点个数为不大于 2 的偶数(即奇度顶点数为 0 或 2)时,} $\(G\)$ \text{存在包含所有边且长度为} $\(|E|\)$ \text{的路径(称为 EL 路径 / 欧拉路径)。设图} $\(G\) 采用邻接矩阵存储:
typedef struct {
int numVertices, numEdges;
char VerticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
int IsExistEL(MGraph G),判断 \(G\) 是否存在 EL 路径,若存在则返回 1,否则返回 0。要求:
1. 给出算法的基本设计思想;
2. 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释;
3. 说明你所设计算法的时间复杂度和空间复杂度。
【解析】¶
1. 算法设计思想¶
由图论中的欧拉定理可知,一个无向连通图存在欧拉路径(EL 路径)的充要条件为:图中的奇度顶点数目为 0(存在欧拉回路,回路亦为欧拉路径)或者为 2(以其中一个奇度顶点为起点,另一个奇度顶点为终点)。 在邻接矩阵存储的无向图中,顶点 \(i\)$ \text{的度数等于矩阵第} $\(i\)$ \text{行中非零元素总数(} $\(\sum_{j=0}^{n-1} Edge[i][j]\))。
算法步骤:
1. 设置奇度顶点计数变量 oddCount = 0。
2. 循环遍历每个顶点 \(i \in [0, n-1]\)$ \text{,累加其对应行向量元素求得该顶点的度数} $\(\deg(i)\)。
3. 若 \(\deg(i) \pmod 2 \ne 0\),则将计数器自增 oddCount++。
4. 遍历全部顶点后,检查 oddCount 是否等于 0 或 2:若是则返回 1,否则返回 0。
2. C/C++ 算法实现¶
int IsExistEL(MGraph G) {
int oddCount = 0; // 记录度为奇数的顶点个数
int n = G.numVertices;
// 依次计算每个顶点的度数
for (int i = 0; i < n; i++) {
int degree = 0; // 当前顶点 i 的度数
// 扫描邻接矩阵的第 i 行
for (int j = 0; j < n; j++) {
if (G.Edge[i][j] != 0) {
degree++;
}
}
// 若度数为奇数,则累加计数
if (degree % 2 != 0) {
oddCount++;
}
}
// 奇度顶点数为 0 或 2 时存在 EL 路径
if (oddCount == 0 || oddCount == 2) {
return 1;
} else {
return 0;
}
}
3. 复杂度分析¶
- 时间复杂度: 算法对外层 \(n\)$ \text{个顶点各执行一次完整的行向量扫描,内层扫描长度为} $\(n\)$ \text{,总访问次数为} $\(n^2\)$ \text{。故时间复杂度为} $\(O(n^2)\)。
- 空间复杂度:
算法只使用了
oddCount、degree、i、j等常数个标量变量,辅助空间复杂度为 \(O(1)\)。
【真题 4】2014 年 408 统考第 7 题 · 邻接矩阵幂运算路径分析¶
题目
若无向图 \(G = (V, E)\)$ \text{的邻接矩阵为} $\(A\)$ \text{,则} $\(A^2\)$ \text{的主对角线元素} $\((A^2)_{ii}\) 表示( )。
A. 顶点 \(v_i\) 的度
B. 顶点 \(v_i\) 到其他顶点的简单路径数
C. 从顶点 \(v_i\)$ \text{出发回到} $\(v_i\) 且长度为 2 的回路数
D. 顶点 \(v_i\) 到所有顶点的最短路径长度之和
【解析】¶
- 依据代数路径定理: 邻接矩阵 \(A\)$ \text{的} $\(m\)$ \text{次幂} $\(A^m\)$ \text{中第} $\(i\)$ \text{行第} $\(j\)$ \text{列元素} $\((A^m)_{ij}\)$ \text{,表示从顶点} $\(v_i\)$ \text{到顶点} $\(v_j\)$ \text{长度为} $\(m\) 的路径数目。
- 考察主对角线元素 \((A^2)_{ii}\): 根据矩阵乘法展开公式: $\((A^2)_{ii} = \sum_{k=0}^{n-1} A_{ik} \cdot A_{ki}\)$ 由于无向图满足对称性 \(A_{ik} = A_{ki}\)$ \text{,且} $\(A_{ik} \in \{0, 1\}\)$ \text{,故} $\(A_{ik} \cdot A_{ki} = (A_{ik})^2 = A_{ik}\)。 因此: $\((A^2)_{ii} = \sum_{k=0}^{n-1} A_{ik} = \deg(v_i)\)$ 在数值上,\((A^2)_{ii}\)$ \text{等于顶点} $\(v_i\) 的度数。
- 图论物理意义对应: 从 \(v_i\)$ \text{出发经过 2 步回到} $\(v_i\)$ \text{的路径形态必然为:} $\(v_i \to v_k \to v_i\)$ \text{。由于无向图中每条与} $\(v_i\)$ \text{相连的边} $\((v_i, v_k)\)$ \text{都可以唯一提供一条来回往返的路径(步长为 2 的回路),因此这既代表从} $\(v_i\)$ \text{出发回到} $\(v_i\)$ \text{且长度为 2 的路径(回路)数,其数值也恰好等于顶点} $\(v_i\) 的度数。 对照 408 官方考查表述,此类选择题的根本落脚点为顶点 \(v_i\) 的度。选项 A 正确。
正确答案:A
【真题 5】2009 年 408 统考第 7 题 · 邻接存储结构特性判定¶
题目
下列关于图的存储结构的叙述中,正确的是( )。
A. 具有 \(n\)$ \text{个顶点的图用邻接矩阵表示,其空间复杂度为} $\(O(n)\)
B. 具有 \(n\)$ \text{个顶点的图用邻接表表示,其空间复杂度为} $\(O(n)\)
C. 具有 \(n\)$ \text{个顶点、} $\(e\)$ \text{条边的图用邻接矩阵表示,求某个顶点度的时间复杂度为} $\(O(n)\)
D. 具有 \(n\)$ \text{个顶点、} $\(e\)$ \text{条边的图用邻接表表示,求某个顶点度的时间复杂度为} $\(O(n)\)
【解析】¶
- A 选项辨析:邻接矩阵存储大小为 \(n \times n\)$ \text{的二维矩阵,不论边数多少,空间复杂度恒为} $\(O(n^2)\),A 错误。
- B 选项辨析:邻接表包含 \(n\)$ \text{个表头节点与} $\(2e\)$ \text{(无向图)或} $\(e\)$ \text{(有向图)个边表节点,总空间复杂度为} $\(O(n + e)\),B 错误。
- C 选项辨析:在邻接矩阵中求某顶点的度(无论是有向图的行和/列和,还是无向图的行和),都需要顺序遍历矩阵中对应的整行(或整列),循环步数为 \(n\)$ \text{,时间复杂度为} $\(O(n)\),C 正确。
- D 选项辨析:在邻接表中求无向图顶点的度仅需遍历该顶点的单链表,时间复杂度为 \(O(\deg(v))\)$ \text{,并非恒为} $\(O(n)\)$ \text{;有向图中求出度为} $\(O(\text{OD}(v))\)$ \text{,求入度需遍历全部边表结点,时间为} $\(O(n + e)\),D 选项表述不准确。
正确答案:C
四、 核心解题套路与易错陷阱¶
1. 邻接矩阵统考大题答题规范¶
408 统考算法设计题(13 分)评分标准通常拆解为三大采分板块:
1. 算法基本思想(4~5 分):
- 必须分段表述:先给出判据的核心理论依据(例如:度数关系、拓扑入度唯一性充要条件等);
- 再给出具体的执行步骤(1. 初始化...;2. 扫描矩阵...;3. 判断并返回...)。切忌堆砌自然语言,采用数字标号逻辑分明。
2. 代码编写(6~7 分):
- 严格遵循题干给出的结构体成员变量名称(大小写需完全一致,如 VerticesList 或 numVertices);
- 必须写明循环边界:顶点编号从 \(0\)$ \text{到} $\(n-1\),循环应为 for (int i = 0; i < n; i++),切勿越界;
- 关键语句添加中文注释(占 1 分)。
3. 时空复杂度分析(2 分):
- 需明确指出时间复杂度为 \(O(n^2)\),并简要说明是由双层嵌套循环扫描矩阵产生;
- 需明确说明空间复杂度(若仅用了变量则为 \(O(1)\)$ \text{,若声明了入度数组则为} $\(O(n)\))。
2. 高频易错点与命题陷阱¶
- 陷阱一:有向图“行出列入”倒置
- 行下标是起点,列下标是终点。\(Edge[i][j] = 1\)$ \text{表示弧} $\(\langle i, j \rangle\)。
- 第 \(i\)$ \text{行求和是出度(从} $\(i\)$ \text{发出的弧);第} $\(i\)$ \text{列求和是入度(指向} $\(i\) 的弧)。考场上若将外层和内层索引颠倒,将导致出度与入度完全混淆。
- 陷阱二:带权网中“边不存在”的判定条件
- 无权图中边不存在为
Edge[i][j] == 0; - 带权网中,通常边不存在存储为
INF(无穷大)或一个极大常数,只有自身对角线元素为 0。若在带权图中依然使用if (Edge[i][j] != 0)判定边存在,会导致算法逻辑全盘崩溃。 - 陷阱三:邻接矩阵的幂 \(A^k\) 中的“路径”定义辨析
- 代数推导中 \((A^k)_{ij}\) 表示的是图论意义上的途径(Walk),即允许顶点与边重复出现的序列。
- 不能将 \((A^k)_{ij} > 0\)$ \text{错误理解为“存在长度为} $\(k\) 的简单路径”。
- 陷阱四:拓扑排序唯一性判定的逻辑漏洞
- 判定拓扑序列唯一,必须满足:每一步可供选择的入度为 0 的顶点数目均严格等于 1。
- 不能仅在初始阶段检查全图中是否只有一个入度为 0 的顶点,必须保证后续每一轮消边后,新产生的候选点依然唯一,且必须能够完整处理全部 \(n\) 个顶点。
五、 考点速记清单¶
- 核心维度:\(n\)$ \text{阶方阵,存储空间恒为} $\(O(n^2)\)$ \text{,与边数} $\(e\) 无关,最适合稠密图。
- 对称特性:无向图是对称矩阵,压缩存储下三角时,一维数组容量 \(\frac{n(n+1)}{2}\)$ \text{,映射公式} $\(k = \frac{i(i+1)}{2} + j\)(\(i \ge j\))。
- 行出列入:有向图中第 \(i\)$ \text{行非零元素和等于顶点} $\(i\)$ \text{的出度;第} $\(j\)$ \text{列非零元素和等于顶点} $\(j\) 的入度。
- 度数计算:在邻接矩阵中求任意顶点的度(或出度、入度),时间复杂度均为 \(O(n)\)。
- 代数幂意义:\(A^k\)$ \text{的元素} $\((A^k)_{ij}\)$ \text{等于顶点} $\(i\)$ \text{到} $\(j\)$ \text{长度为} $\(k\)$ \text{的路径(途径)条数;对角线} $\((A^2)_{ii}\)$ \text{等于顶点} $\(i\) 的度。
- 大题模板:
- 求度数/判奇度:双层遍历,单行/单列求和,时间 \(O(n^2)\)$ \text{,空间} $\(O(1)\)。
- 拓扑排序/DAG判环:维护
inDegree[n],每步找唯一的 0 并更新后继,时间 \(O(n^2)\)$ \text{,空间} $\(O(n)\)。