跳转至

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\) 的路径数目之间的图论代数定理推导。
近十年考查年份分布:
2016   2017   2018   2019   2020    2021    2022    2023    2024    2025
 -      -      -      -      -       √       -       √       √       -
                                   (#41)           (#41)   (#41)

二、 具体考察内容

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;
将图中出度大于入度的顶点称为 K 顶点。例如某顶点 \(v\) 出度为 3,入度为 2,则该顶点为 K 顶点。
设计算法 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\) 到所有顶点的最短路径长度之和

【解析】

  1. 依据代数路径定理: 邻接矩阵 \(A\)$ \text{的} $\(m\)$ \text{次幂} $\(A^m\)$ \text{中第} $\(i\)$ \text{行第} $\(j\)$ \text{列元素} $\((A^m)_{ij}\)$ \text{,表示从顶点} $\(v_i\)$ \text{到顶点} $\(v_j\)$ \text{长度为} $\(m\) 的路径数目。
  2. 考察主对角线元素 \((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\) 的度数。
  3. 图论物理意义对应: 从 \(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\) 个顶点。

五、 考点速记清单

  1. 核心维度:\(n\)$ \text{阶方阵,存储空间恒为} $\(O(n^2)\)$ \text{,与边数} $\(e\) 无关,最适合稠密图。
  2. 对称特性:无向图是对称矩阵,压缩存储下三角时,一维数组容量 \(\frac{n(n+1)}{2}\)$ \text{,映射公式} $\(k = \frac{i(i+1)}{2} + j\)(\(i \ge j\))。
  3. 行出列入:有向图中第 \(i\)$ \text{行非零元素和等于顶点} $\(i\)$ \text{的出度;第} $\(j\)$ \text{列非零元素和等于顶点} $\(j\) 的入度。
  4. 度数计算:在邻接矩阵中求任意顶点的度(或出度、入度),时间复杂度均为 \(O(n)\)。
  5. 代数幂意义:\(A^k\)$ \text{的元素} $\((A^k)_{ij}\)$ \text{等于顶点} $\(i\)$ \text{到} $\(j\)$ \text{长度为} $\(k\)$ \text{的路径(途径)条数;对角线} $\((A^2)_{ii}\)$ \text{等于顶点} $\(i\) 的度。
  6. 大题模板:
  7. 求度数/判奇度:双层遍历,单行/单列求和,时间 \(O(n^2)\)$ \text{,空间} $\(O(1)\)。
  8. 拓扑排序/DAG判环:维护 inDegree[n],每步找唯一的 0 并更新后继,时间 \(O(n^2)\)$ \text{,空间} $\(O(n)\)。