🏷️ 知识点：邻接矩阵

共 18 道相关题目

2012 年第 6 题数据结构选择题

若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。

拓扑排序

A. 存在，且唯一

B. 存在，且不唯一

C. 存在，可能不唯一

D. 无法确定是否存在

[tag_link]

正确答案：C

主对角线以下元素均为零，表示只可能存在 i→j (i<j) 的边，不可能沿边从较大编号回到较小编号，所以图中无有向环，一定存在拓扑序列。

但拓扑序列未必唯一。例如 3 个顶点只有边 1→3、2→3 时，邻接矩阵是严格上三角矩阵，1,2,3 与 2,1,3 都是合法拓扑序。因此选 C。

反过来，DAG 在任意编号下的邻接矩阵未必是三角矩阵；按某个拓扑序给顶点重新编号后，才可得到严格上三角矩阵。

模拟卷年第 7 题数据结构选择题

一个含有 $n$ 个顶点和 $e$ 条边的简单无向图，其邻接矩阵存储中零元素的个数是（）。

A. $e$ B. $2 e$ C. $n^{2} - e$ D. $n^{2} - 2 e$

邻接矩阵

[tag_link]

正确答案：D

邻接矩阵是一个 $n \times n$ 的矩阵，总共有 $n^{2}$ 个元素。在简单无向图中，没有自环，因此对角线上的 $n$ 个元素均为零。图的每条边对应两个对称的非对角线元素（例如，边 $(i, j)$ 对应 $A [i] [j]$ 和 $A [j] [i]$ ），所以非零元素的个数为 $2 e$ 。零元素的个数等于总元素数减去非零元素数，即 $n^{2} - 2 e$ 。

2013 年第 7 题数据结构选择题

设图的邻接矩阵 A 如下所示。各顶点的度依次是（）

A=0001101001001100

邻接矩阵

A.1，2，1，2

B.2，2，1，1

C.3，4，2，3

D.4，4，2，2

[tag_link] 正确答案：C 邻接矩阵 A 为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。

课后题年第 16 题数据结构选择题

下列关于图的存储结构的说法中，错误的是（）。

A. 使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数有关，与边数无关 B. 邻接表只用于有向图的存储，逆邻接表只用于无向图的存储 C. 若一个有向图的邻接矩阵的主对角线以下元素全为 0，则边只由小编号顶点指向大编号顶点，该图无环且必定存在拓扑序列（不保证唯一） D. 存储无向图的邻接矩阵是对称的，所以只需存储邻接矩阵的下（或上）三角部分

[tag_link]

正确答案：B

结论

错误的是 B。邻接表既可表示有向图，也可表示无向图；逆邻接表同样服务于有向图的入边访问。

推导

邻接矩阵始终按顶点对分配空间，未压缩时为 (O(n^2))，与边数无关。无向图矩阵对称，可只保存一侧三角区；若有向图矩阵主对角线以下全为 0，所有边均从小编号指向大编号，因而不可能成环，按编号升序即可得到一个拓扑序列。

易错点

不要把“邻接表”和“逆邻接表”误认为只适用于某一种图：邻接表通常记录出边，逆邻接表记录入边，二者主要用于有向图的不同访问方向；无向图也可用邻接表表示。

课后题年第 17 题数据结构选择题

若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则该图一定（）。

A. 是无向图 B. 是有向图 C. 是完全图 D. 不是带权图

[tag_link]

正确答案：C

结论

该图一定是完全图，答案为 C。

推导

主对角线全为 0 表示没有自环；其余 (n(n-1)) 个位置全为 1，表示任意两个不同顶点之间都存在相应连接。在简单图的邻接矩阵约定下，每一对不同顶点均相邻，故为完全图。

易错点

矩阵是否对称才能进一步判断有向或无向；题干只给出对角线和非对角线取值，不能据此断言图的方向性。矩阵元素为 1 也不排斥“无权表示”，所以“不是带权图”不是必然结论。

课后题年第 18 题数据结构选择题

在含有 (n) 个顶点和 (e) 条边的简单无向图的邻接矩阵中，零元素的个数为（）。

A. (e) B. (2e) C. (n^2-e) D. (n^2-2e)

[tag_link]

正确答案：D

结论

零元素的个数为 (n^2-2e)，答案为 D。

推导

邻接矩阵共有 (n^2) 个位置。简单无向图没有自环，且每条无向边在矩阵中占据对称的两个非零位置，因此非零位置数为 (2e)，零元素数为 (n^2-2e)。

易错点

不能把每条无向边只计一次；矩阵同时记录 ((i,j)) 和 ((j,i))。若题目允许自环或使用其他特殊编码，公式需重新判断，本题明确按简单无向图处理。

课后题年第 19 题数据结构选择题

带权有向图 (G) 用邻接矩阵存储，约定无边位置为 (\infty)（对角线为 0），则顶点 (v_i) 的入度等于邻接矩阵中（）。

A. 第 (i) 行非 (\infty) 的元素个数 B. 第 (i) 列非 (\infty) 的元素个数 C. 第 (i) 行非 (\infty) 且非 0 的元素个数 D. 第 (i) 列非 (\infty) 且非 0 的元素个数

[tag_link]

正确答案：D

结论

答案为 D：扫描第 (i) 列，统计既不是 (\infty) 又不是 0 的元素。

推导

邻接矩阵的第 (j) 行第 (i) 列元素表示边 (v_j\to v_i) 的权值。第 (i) 列中每个有限且非零的权值对应一条进入 (v_i) 的边，因此其个数就是入度；第 (i) 行统计的是出度。

易错点

入度与出度的方向相反：入度看列，出度看行。带权矩阵中不能只判断“非 (\infty)”——对角线的 0 表示无自环，必须同时排除 0。

课后题年第 36 题数据结构综合题

对 n 个顶点的无向图和有向图，分别采用邻接矩阵和邻接表表示时，试问：

如何判别图中有多少条边？
如何判别任意两个顶点 i 和 j 是否有边相连？
任意一个顶点的度是多少？

[tag_link]

参考答案

1. 边数

邻接矩阵：无向图的非零（无权图即为 1）元素数为 2e，边数为非零元素数除以 2；有向图的非零元素数就是弧数 e。
邻接表：无向图每条边有两个边表结点，边数为边表结点总数除以 2；有向图的边表结点总数就是弧数。

2. 判断相邻

邻接矩阵中，无向图检查 A[i][j]（等价地检查 A[j][i]），有向图检查 A[i][j] 是否表示弧 i→j。邻接表中，扫描顶点 i 的边链表查找 j；无向图还可从 j 的链表查找 i。

3. 顶点度

邻接矩阵中，无向图顶点 i 的度是第 i 行（或列）的非零元素数；有向图第 i 行非零元素数为出度，第 i 列非零元素数为入度，度为二者之和。邻接表中，无向图顶点 i 的度是其边链表长度；有向图该链表长度为出度，入度需统计所有边表中指向 i 的结点，度为入度与出度之和。

易错点

无向图邻接表的边存储两次，而有向图每条弧只存储一次；有向图邻接表的链表长度只是出度，不能直接当作总度。

课后题年第 37 题数据结构综合题

如何对无环有向图中的顶点重新编号，使得该图的邻接矩阵中所有的 1 都集中到对角线以上？

[tag_link]

参考答案

对该 DAG 进行拓扑排序，并按拓扑序列依次编号为 1,2,…,n。对任意弧 i→j，拓扑序都要求 i 排在 j 之前，因此新编号满足 i<j；对应的邻接矩阵元素 A[i][j] 只可能位于主对角线上方。拓扑排序可用入度为 0 的顶点逐步删除，若有多个候选顶点，任取其一即可。

推导

DAG 必然存在拓扑序。重新编号后，若矩阵下三角位置 A[i][j]（i>j）为 1，就表示存在弧 i→j，与拓扑序中 i 应排在 j 前矛盾。因此所有 1 均在主对角线上方；该性质不要求拓扑序唯一。

易错点

只按原编号排序不一定成立；必须使用拓扑序。矩阵上三角方向取决于约定的弧方向和编号顺序，本文约定 A[i][j]=1 表示 i→j。

课后题年第 38 题数据结构综合题

写出从图的邻接表表示转换成邻接矩阵表示的算法。

[tag_link]

参考答案

设图有 n 个顶点，邻接矩阵为 A。先将 A 的 n×n 元素初始化为 0；再依次扫描每个顶点 i 的边链表，对其中每条边 i→j 置 A[i][j]=1。若为无向图，边结点按邻接表约定会在两个端点链表中出现，仍按扫描结果赋值即可。

for i = 0..n-1:
    for j = 0..n-1:
        A[i][j] = 0
for i = 0..n-1:
    p = Adj[i].first
    while p != null:
        A[i][p.adjvex] = 1
        p = p.next

初始化矩阵需要 O(n²)，扫描顶点表和全部边表需要 O(n+e)（无向图的边表结点数为 2e，仍为 O(n+e)），所以严格总复杂度为 O(n²+n+e)=O(n²+e)，空间复杂度为 O(n²)。若题目约定矩阵已预先清零，则只计转换扫描部分，为 O(n+e)。

易错点

不能只遍历一个顶点的链表，也不能把无向图的两次边表出现误算成两条不同的边；初始化复杂度与填边扫描复杂度要分别说明。

2011 年第 41 题数据结构综合题

已知有 6 个顶点（顶点编号为 0～5）的有向带权图 G ，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

(1) 写出图 G 的邻接矩阵 A 。

(2) 画出有向带权图 G 。

(3) 求图 G 的关键路径，并计算该关键路径的长度。

邻接矩阵关键路径

[tag_link]

1）上三角矩阵 A[6][6] 中，第 1 行至第 5 行主对角线上方的元素个数分别为 5, 4, 3, 2, 1,由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。用“平移”的思想，将前 5 个、后 4 个、后 3 个、后 2 个、后 1 个元素，分别移动到矩阵对角线 (“0”) 右边的行上。图 G 的邻接矩阵 A 如下所示。

2）据上面的邻接矩阵，画出有向带权图 G, 如下图所示。

(3) 按照算法，先计算各个事件的最早发生时间，计算过程如下：ve(0)=0;ve(1)=ve(0)+a0→1=4;ve(

2)=max(ve(0)+a0→1,ve(

1)+a1→2)=max(6,4+

5)=9;ve(

3)=ve(

2)+a2→3=9+4=13;ve(

4)=ve(

2)+a2→4=9+3=12;ve(

5)=max(ve(

3)+a3→5,ve(

4)+a4→5)=max(16,1

5)=16;接下来求各个时间的最迟发生时间，计算过程如下：vl(

5)=ve(

5)=16;vl(

4)=vl(

5)−a4→5=16−3=13;vl(

3)=vl(

5)−a3→5=16−3=13;vl(

2)=min(vl(

3)−a2→3,vl(

4)−a2→4)=min(9,10)=9;vl(

1)=vl(

2)−a1→2=4;vl(0)=min(vl(

2)−a0→2,vl(

1)−a0→1)=min(3,0)=0;即 ve() 和 vl() 数组如下表所示。

i	0	1	2	3	4	5
ve(i)	0	4	9	13	12	16
vl(i)	0	4	9	13	13	16

接下来计算所有活动的最早和最迟发生时间 e() 和 l()：e(a0→1)=e(a0→2)=ve(0)=0;e(a1→2)=ve(1)=4;e(a2→3)=e(a2→4)=ve(2)=9;e(a3→5)=ve(3)=13;e(a4→5)=ve(4)=12;l(a4→5)=vl(5)−a4→5=16−3=13;l(a3→5)=vl(5)−a3→5=16−3=13;l(a2→4)=vl(4)−a2→4=13−3=10;l(a2→3)=vl(3)−a2→3=13−4=9;l(a1→2)=vl(2)−a1→2=9−5=4;l(a0→2)=vl(2)−a0→2=9−6=3;l(a0→1)=vl(1)−a0→1=4−4=0;e() 和 l() 数组与它们的差值如下表所示。

	a0→2	a1→2	a2→3	a2→4	a3→5	a4→5
e()	0	4	9	9	13	12
l()	3	4	9	10	13	13
l-e	3	0	0	1	0	1

满足 l() - e() = 0 的路径就是关键路径，所以关键路径为a0→1、a1→2、a2→3、a3→5，如下图所示（粗线表示），长度为4+5+4+3=16。

2021 年第 41 题数据结构综合题

已知无向连通图 G 由顶点集 V 和边集 E 组成，|E| > 0，当 G 中度为奇数的顶点个数为不大于 2 的偶数时，G 存在包含所有边且长度为|E|的路径（称为 EL 路径）。设图 G 采用邻接矩阵存储，类型定义如下：

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV 为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则返回 0。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

邻接矩阵

[tag_link]

1）算法的基本设计思想本算法题属于送分题，题干已经告诉我们算法的思想。对于采用邻接矩阵存储的无向图，在邻接矩阵的每一行（列）中，非零元素的个数为本行（列）对应顶点的度。可以依次计算连通图 G 中各顶点的度，并记录度为奇数的顶点个数，若个数为 0 或 2，则返回 1，否则返回 0。

2）算法实现

int isExistEL(MGraph G) {
  // 统计度为奇数的定点个数
  int count = 0;
  for (int v = 0; v < numVertices; v++) {
    // 该顶点的度
    int degree = 0;
    for (int e = 0; e < numEdges; e++) {
      if (Edge[v][e] == 1) {
        degree++;
      }
    }
    if (degree % 2 == 1) {
      count++;
    }
  }
  if (count == 0 || count == 2) {
    return 1;
  }
  return 0;
}

3）时间和空间复杂度算法需要遍历整个矩阵，所以时间复杂度为O(n2)，空间复杂度为O(1)。

2023 年第 41 题数据结构综合题

已知有向图 G 采用邻接矩阵存储，类型定义如下：

typedef struct {                    // 图的类型定义
    int numVertices, numEdges;      // 图中顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表，MAXV 为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

将图中出度大于入度的顶点称为 K 顶点。例如在题 41 图中，顶点 a 和 b 都是 K 顶点。

2018_Q7_3

设计算法 int printVertices(MGraph G) 对给定任意非空有向图 G，输出 G 中所有 K 顶点的算法，并返回 K 顶点的个数。

(1) 给出算法的设计思想。

(2) 根据算法思想，写出 C/C++ 描述，并注释。

邻接矩阵

[tag_link]

1）采用邻接矩阵表示有向图时，一行中 1 的个数为该行对应顶点的出度，一列中 1 的个数为该列对应顶点的入度。使用一个初值为 0 的计数器记录 K 顶点的个数。对图 G 的每个顶点，根据邻接矩阵计算其出度 outdegree 和入度 indegree。若 outdegree - indegree > 0，则输出该顶点且计数器加 1。最后返回计数器的值。

2）算法实现

int printVertices(MGraph G) {
    // K 顶点的个数
    int count = 0;
    for (int v = 0; v < numVertices; v++) {
        // v 顶点的入度和出度
        int indegree = 0;
        int outdegree = 0;
        // 统计出度
        for (int i = 0; i < numVertices; i++) {
            outdegree += G.Edge[v][i];
        }
        // 统计入度
        for (int i = 0; i < numVertices; i++) {
            indegree += G.Edge[i][v];
        }
        if (outdegree > indegree) {
            printf("%s ", G.VerticesList[v]);
            count++;
        }
    }
    return count;
}

2024 年第 41 题数据结构综合题

2023 年 10 月 26 日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导工程。以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已如有向图 G 采用邻接矩阵存储，类型定义如下：

typedef struct // 图的类型定义
{
    int numVertices, numEdges; // 图的顶点数和有向边数
    char verticesList[MAXV];   // 项点表，MAXV 为以定义常量
    int Edge[MAXV][MAXV];      // 邻接矩阵
} MGraph

请设计算法：int uniquely(MGraph G)。判定 G 是否存在唯一的拓扑序列，若是则返回 1，否则返回 0。要求：

(1) 给出算法的基本设计思想（4 分）

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释（9 分）

拓扑排序邻接矩阵

[tag_link]

1）算法基本设计思想输出拓扑序列的过程如下：依次从图中选取入度为 0 的点进行输出。确保拓扑序列唯一需要保证如下条件：在输出拓扑序列时，每一次有且仅有一个入度为 0 的顶点。所以这题最直观的思路就是进行 numEdges 轮遍历，如果每轮遍历只有一个顶点的入度为 0，则图中存在唯一的拓扑序列；否则不存在唯一的拓扑序列。

2）算法实现

int uniquely(MGraph g)
{
    int n = g.numVertices;
    int inDegrees[MAXV];

    /* 计算所有顶点的入度 */
    for (int v = 0; v < n; v++) {
        inDegrees[v] = 0;
        for (int i = 0; i < n; i++) {
            if (g.Edge[i][v] != 0)
                inDegrees[v] += g.Edge[i][v];
        }
    }

    /* 进行 n 轮拓扑删除 */
    for (int k = 0; k < n; k++) {

        int count0 = 0;   // 入度为 0 的顶点个数
        int v0 = -1;      // 本轮唯一可以选择的顶点

        /* 找所有入度为 0 的顶点 */
        for (int i = 0; i < n; i++) {
            if (inDegrees[i] == 0) {
                count0++;
                v0 = i;
            }
        }

        /* 若不是唯一一个，则拓扑序列不唯一 */
        if (count0 != 1) {
            return 0;
        }

        /* “删除”该顶点：将其入度设为 -1，避免重复选取 */
        inDegrees[v0] = -1;

        /* 更新其所有后继节点的入度 */
        for (int j = 0; j < n; j++) {
            if (g.Edge[v0][j] != 0)
                inDegrees[j]--;
        }
    }

    /* 所有步骤都唯一，拓扑序唯一 */
    return 1;
}

2015 年第 42 题数据结构综合题

[tag_link]

已知含有5个顶点的图G如下图所示。

2012_Q41_1

请回答下列问题：

(1) 写出图G的邻接矩阵A（行、列下标均从0开始）。

(2) 求A2，矩阵A2中位于 0 行 3 列元素值的含义是什么？

(3) 若已知具有n(n≥2)个顶点的图的邻接矩阵为B，则Bm(2≤m≤n)中非零元素的含义是什么？

邻接矩阵

1）图A的邻接矩阵如下：

	1	2	3	4	5
1	0	1	1	0	1
2	1	0	0	1	1
3	1	0	0	1	0
4	0	1	1	0	1
5	1	1	0	1	0

2）A2如下：0 行 3 列的元素值 3 表示从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。

	1	2	3	4	5
1	3	1	0	3	1
2	1	3	2	1	2
3	0	2	2	0	2
4	3	1	0	3	1
5	1	2	2	1	3

3）Bm(2≤m≤n) 中位于i行j列（0≤i,j≤n−1）的非零元素的含义是：图中从顶点i到顶点j长度为m的路径条数。

课后题年第 56 题数据结构选择题

下列哪种图的邻接矩阵是对称矩阵？（）

A. 有向网 B. 无向图 C. AOV 网 D. AOE 网

正确答案：B

结论

B 无向图的邻接矩阵必为对称矩阵。

推导

无向边 {vᵢ,vⱼ} 同时表示 i 到 j、j 到 i，因此矩阵中 aᵢⱼ=aⱼᵢ；无自环时主对角线为 0。

易错点

A 有向网不保证对称；C AOV 网和 D AOE 网都是有向网络，边方向也不保证对称。

课后题年第 57 题数据结构选择题

若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为（）。

A. 对称 B. 稀疏 C. 三角 D. 一般

正确答案：C

结论

C。按拓扑序给顶点编号后，邻接矩阵必为严格上三角或严格下三角矩阵。

推导

拓扑序要求每条边都从序号较小顶点指向序号较大顶点，所以一种编号方向下非零元素只在主对角线上方；若反向编号，则只在下方。无自环时主对角线为 0。

易错点

A 对称性属于无向图；B 拓扑序不限制边数，不能推出稀疏；D 忽略了拓扑序带来的方向约束。

王道整理题年第 64 题数据结构选择题

在求 AOE网的关键路径时，若该有向图用邻接矩阵表示且第i 列值全为∞，则（）。

A. 若关键路径存在，第i 个顶点一定是起点 B. 若关键路径存在，第i 个顶点一定是终点 C. 关键路径不存在 D. 该有向图对应的无向图存在多个连通分量

正确答案：A

结论

选 A。在矩阵约定 a[u][v] 表示 u→v 时，第 i 列全为 ∞ 表示没有入边，即顶点 i 入度为零；在 AOE 网存在关键路径且源点唯一的前提下，它就是起点。

推导

邻接矩阵的列统计入边、行统计出边。入度为零的顶点只能作为工程源点候选；“关键路径存在”以及 AOE 网通常要求唯一源点，才可判定为起点。详见邻接矩阵列与入度。

易错点

列全 ∞ 只说明无入边，不说明终点（终点应看出度为零，即行全 ∞），也不能单独推出图不连通；必须结合 AOE 网的单一源点和关键路径存在前提。

← 返回真题分析