数据结构之图的存储

图的存储及基本操作

邻接矩阵法

定义：邻接矩阵存储图的顶点和边的信息。用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。对于一个含有 $ n $ 个顶点的图 $ G = (V, E) $，其邻接矩阵 $ A $ 是一个 $ n n $ 的矩阵。

将 $ G $ 的顶点编号为 $ V_1, V_2, , V_n $。
如果边 $ (V_i, V_j) E $，则 $ A[i][j] = 1 $（对于无权图）或 $ A[i][j] = w $（对于带权图），其中 $ w $ 是边的权值。
如果边 $ (V_i, V_j) E $，则 $ A[i][j] = 0 $（或用无穷大表示）。

邻接矩阵的存储结构定义

#define MaxVertexNum 100
typedef char VertexType;   // 顶点的数据类型
typedef int EdgeType;      // 带权图中边上权值的数据类型

typedef struct {
    VertexType vex[MaxVertexNum];        // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
    int vexnum;                          // 图的当前顶点数
    int arcnum;                          // 图的当前边数
} MGraph;

邻接矩阵的特性

对称性：
- 对于无向图，邻接矩阵是一个对称矩阵；即 $ A[i][j] = A[j][i] $。
- 因此，存储时只需保存上三角或下三角的元素。
度的计算：
- 对于无向图，邻接矩阵的第 $ i $ 行（或第 $ i $ 列）非零元素的个数等于顶点 $ V_i $ 的度 $ TD(V_i) $。
- 对于有向图，邻接矩阵的第 $ i $ 行非零元素的个数等于顶点 $ V_i $ 的出度 $ OD(V_i) $，而第 $ i $ 列非零元素的个数等于入度 $ ID(V_i) $。
边的检测：
- 用邻接矩阵存储图，容易确定任意两个顶点之间是否有边相连。
- 但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，这在时间上代价较大。
适用性：
- 邻接矩阵适合于稠密图的存储表示。

附加性质

设图 $ G $ 的邻接矩阵为 $ A $，若 $ A^{(n)}[i][j] $ 表示从顶点 $ i $ 到顶点 $ j $ 的长度为 $ n $ 的路径的数量，则该结论可以参考离散数学教材进行证明。

定义：
设图 $ G $ 的邻接矩阵为 $ A $，则：

$ A[i][j] = 1 $ 表示存在一条从顶点 $ i $ 到顶点 $ j $ 的边。

$ A[i][j] = 0 $ 表示顶点 $ i $ 和顶点 $ j $ 之间没有边。

结论：
通过矩阵的乘法，我们可以得出 $ A^{(k)}[i][j] $ 表示从顶点 $ i $ 到顶点 $ j $ 的长度为 $ k $ 的路径数量。

证明过程：

基础情况（$ n = 1 $）：

对于 $ A^{(1)} $，每个元素 $ A^{(1)}[i][j] $ 直接表示从顶点 $ i $ 到顶点 $ j $ 的边的数量。

因此，$ A^{(1)}[i][j] = A[i][j] $。

归纳假设：

假设对于 $ n = k $，$ A^{(k)}[i][j] $ 表示从顶点 $ i $ 到顶点 $ j $ 的长度为 $ k $ 的路径的数量。

归纳步骤（$ n = k + 1 $）：

要计算 $ A^{(k + 1)}[i][j] $，我们可以通过所有可能的中间顶点来连接路径。具体来说：$ A^{(k + 1)}[i][j] = _{t=1}^{n} A^{(k)}[i][t] A[t][j] $

这里的 $ t $ 表示中间顶点的遍历。

$ A^{(k)}[i][t] $ 表示从顶点 $ i $ 到顶点 $ t $ 的长度为 $ k $ 的路径数量，而 $ A[t][j] $ 表示从顶点 $ t $ 到顶点 $ j $ 的边的数量（即长度为 1 的路径）。

通过遍历所有中间顶点 $ t $，我们可以得到从 $ i $ 到 $ j $ 的长度为 $ k + 1 $ 的所有路径数量。

总结归纳：

因此，由于对基础情况和归纳步骤的验证，得出结论：对于任意正整数 $ n $，$ A^{(n)}[i][j] $ 表示从顶点 $ i $ 到顶点 $ j $ 的长度为 $ n $ 的路径的数量。

邻接表法

邻接表是一种用于存储图的高效数据结构，特别适合稀疏图。其基本思想是为图中的每个顶点建立一个链表，链表中的每个节点表示与该顶点相连的边。

1. 结构定义

图的邻接表存储结构定义如下：

#define MaxVertexNum 100

typedef struct arcNode {
    int adjvex; // 该弧所指向的顶点的位置
    struct arcNode *next; // 指向下一条弧的指针
    // InfoType info; // 图中边的权值（可选）
} ArcNode;

typedef struct {
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode;

typedef ArcNode *AdjList[MaxVertexNum]; // 邻接表
typedef struct {
    AdjList vertices; // 顶点表
    int vexnum; // 图的顶点数
    int arcnum; // 图的边数
} ALGraph; // ALGraph是以邻接表存储的图类型

2. 存储特点

存储空间：
- 对于无向图，所需的存储空间为 $ O(V + 2E) $，其中 $ V $ 是顶点数，$ E $ 是边数。由于每条边在邻接表中出现两次，故有 $ 2E $。
- 对于有向图，所需的存储空间为 $ O(V + E) $。
适合稀疏图：
- 对于稀疏图，邻接表的存储方式可以显著节省存储空间，相较于邻接矩阵，存储效率更高。

3. 操作效率

查找邻边：
- 给定一个顶点，找到其所有邻边非常方便，只需读取其邻接表，时间复杂度为 $ O(1) $。
- 在邻接矩阵中，同样的操作需要扫描一整行，时间复杂度为 $ O(V) $。
判断边的存在性：
- 在邻接矩阵中，可以立即查找给定的两个顶点间是否存在边，时间复杂度为 $ O(1) $。
- 在邻接表中，需要遍历相应的边表来查找另一顶点，效率较低。

4. 入度和出度计算

出度：
- 在有向图的邻接表中，求给定顶点的出度只需计算其邻接表中的节点个数。
入度：
- 计算入度则需要遍历所有的邻接表，效率较低。
- 为了加速求解入度，可以采用逆邻接表的存储方式，类似于邻接表。

5. 不唯一性

邻接表的表示并不唯一，因为在每个顶点对应的单链表中，边节点的链接顺序可以是任意的。这取决于建立邻接表的算法及边的输入顺序。

十字链表

十字链表是一种用于有向图的链式存储结构，它为每条弧（有向边）和每个顶点提供了有效的存储方式，使得图的遍历和操作更加高效。

1. 结构定义

弧节点结构：

弧节点包含以下五个域：

tailvex: 指示弧的尾部顶点在图中的位置（索引）。
headvex: 指示弧的头部顶点在图中的位置（索引）。
hlink: 指向与当前弧头相同的下一条弧的指针。
tlink: 指向与当前弧尾相同的下一条弧的指针。
info: 存储与该弧相关的信息（例如权值）。

顶点节点结构：

顶点节点包含以下三个域：

data: 存放顶点相关的数据信息（例如顶点名称）。
firstin: 指向以该顶点为弧头的第一个弧节点的指针。
firstout: 指向以该顶点为弧尾的第一个弧节点的指针。

2. 十字链表的特性

双向链表: 十字链表的结构使得对于每个弧，既可以方便地找到以其为尾的弧（outgoing edges），也可以方便地找到以其为头的弧（incoming edges）。
出度和入度: 由于顶点节点直接指向与其相关的弧节点，可以快速计算出度和入度。

3. 存储特点

顺序存储: 顶点节点之间采用顺序存储方式，便于访问。
表示不唯一: 尽管十字链表的表示不唯一，但它的结构可以唯一确定一个有向图。

4. 图的示例

图6.9展示了一个有向图的十字链表表示法。通过这种表示方式，可以快速有效地访问顶点和弧的相关信息。

图的基本操作

图的基本操作是与图的存储结构无关的，但不同的存储方式会影响操作算法的具体实现和性能。在设计图的基本操作时，需要考虑选择合适的存储方式以提高算法的效率。以下是主要的图操作：

判断边的存在性
- Adjacent(G, x, y): 判断图 $ G $ 中是否存在边 $ (x, y) $ 或 $ <x, y> $。
列出邻接边
- Neighbors(G, x): 列出图 $ G $ 中与节点 $ x $ 邻接的边。
插入和删除顶点
- InsertVertex(G, x): 在图 $ G $ 中插入顶点 $ x $。
- DeleteVertex(G, x): 从图 $ G $ 中删除顶点 $ x $。
添加和删除边
- AddEdge(G, x, y): 如果无向边 $ (x, y) $ 或有向边 $ <x, y> $ 不存在，则向图 $ G $ 中添加该边。
- RemoveEdge(G, x, y): 如果无向边 $ (x, y) $ 或有向边 $ <x, y> $ 存在，则从图 $ G $ 中删除该边。
获取邻接点
- FirstNeighbor(G, x): 求图 $ G $ 中顶点 $ x $ 的第一个邻接点，若有则返回该顶点号；若 $ x $ 没有邻接点或图中不存在 $ x $，则返回 -1。
- NextNeighbor(G, x, y): 假设图 $ G $ 中顶点 $ y $ 是顶点 $ x $ 的一个邻接点，返回除 $ y $ 外顶点 $ x $ 的下一个邻接点的顶点号；若 $ y $ 是 $ x $ 的最后一个邻接点，则返回 -1。
获取和设置边的权值
- GetEdgeValue(G, x, y): 获取图 $ G $ 中边 $ (x, y) $ 或 $ <x, y> $ 对应的权值。
- SetEdgeValue(G, x, y, v): 设置图 $ G $ 中边 $ (x, y) $ 或 $ <x, y> $ 对应的权值为 $ v $。
图的遍历
- 图的遍历算法用于按照某种方式访问图中的每个顶点且仅访问一次。主要的遍历算法包括：
  - 深度优先遍历（DFS）
  - 广度优先遍历（BFS）

选择题

01. 关于图的存储结构，( )是错误的。

选项：

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

答案： B

解释：

A. 正确：邻接矩阵的存储空间为 $O(n^2)$，与边数无关。
B. 错误：邻接表不仅可以用于有向图，也可以用于无向图，只是需要存储每条边两次。
C. 正确：如果对角线以下的元素全为0，意味着不存在环，拓扑序列必然存在。
D. 正确：无向图的邻接矩阵确实是对称的，因此只需存储一半的元素。

02. 若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则可以断定该图一定( )。

选项：

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

答案： C

解释：

主对角线上的元素为0表示没有自环，而其余元素全为1表示任意两个不同的顶点之间都有边相连，因此该图是完全图。

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

选项：

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

答案： D

解释：

无向图的邻接矩阵大小为 $n \times n$，其中包含 $n^2$ 个元素。由于每条边在矩阵中对应两个非零元素，故非零元素的个数为 $2e$。因此，零元素的个数为 $n^2 - 2e$。

04. 带权有向图 G 用邻接矩阵存储，则 v 的入度等于邻接矩阵中( )。

选项：

A. 第 i 行非零的元素个数
B. 第 i 列非∞的元素个数
C. 第 i 行非零且非∞的元素个数
D. 第 i 列非∞且非0的元素个数

答案： D

解释：

有向图中，入度是通过邻接矩阵的列来计算的，列中非零且非∞的元素表示从其他顶点指向顶点 $v$ 的边。因此，入度等于第 $i$ 列非∞且非0的元素个数。

05. 一个有n个顶点的图用邻接矩阵A表示，若图为有向图，顶点v的入度是();若图为无向图，顶点v的度是()

选项：

A. $\sum_{j=1}^{n} A[j][v]$
B. $\sum_{j=1}^{n} A[v][j]$
C. $\sum_{j=1}^{n} A[i][j]$
D. $\sum_{i=1}^{n} A[i][j]$

答案： B，D

解释：

有向图的入度：顶点 $v$ 的入度是从其他顶点指向 $v$ 的边的数量，可以通过计算邻接矩阵中第 $v$ 列的非零元素数量得到，即 $\sum_{j=1}^{n} A[j][v]$。
无向图的度：顶点 $v$ 的度是与 $v$ 相连的边的数量，无向图中每条边在邻接矩阵中存储两次，因此可以通过计算第 $v$ 行或第 $v$ 列的非零元素数量得到，即 $\sum_{j=1}^{n} A[v][j]$ 或 $\sum_{j=1}^{n} A[j][v]$，结果相同。

06. 下列哪种图的邻接矩阵是对称矩阵?()

选项：

A. 有向网
B. 无向网
C. 有向有权网
D. 有向无权网

答案： B

解释：

无向图的邻接矩阵：在无向图中，边是无方向的，因此在邻接矩阵中，对于任意一条边 $(i, j)$，都有 $A[i][j] = A[j][i]$。这使得无向图的邻接矩阵是对称矩阵。
有向图的邻接矩阵：在有向图中，边的方向性导致 $A[i][j] \neq A[j][i]$，因此邻接矩阵不是对称的。

07. 从邻接矩阵可以看出，该图共有(①)个顶点;若是有向图，则该图共有(②)条弧;若是无向图，则共有(③)条边。

选项：

①
- A. 9
- B. 3
- C. 6
- D. 1
- E. 以上答案均不正确
②
- A. 5
- B. 4
- C. 3
- D. 2
- E. 以上答案均不正确
③
- A. 5
- B. 4
- C. 3
- D. 2
- E. 以上答案均不正确

答案： ① B（3），② B（4），③ D（2）

解释：

顶点数 (①)：邻接矩阵的行数或列数即为图中的顶点数。如果矩阵的大小是 $3 \times 3$，则图有 3 个顶点。
有向图的弧数 (②)：有向图中的边数量等于邻接矩阵中非零元素的总数。例如，如果在矩阵中发现 4 条弧（非零元素），则答案是 4。
无向图的边数 (③)：无向图中的边数量等于邻接矩阵中非零元素的总数的一半，因为每条边会在矩阵中存储两次（对称）。如果有 4 条弧，则对应的边数为 $ = 2 $。

08. 以下关于图的存储结构的叙述中，正确的是()

选项：

A. 一个图的邻接矩阵表示唯一，邻接表表示唯一
B. 一个图的邻接矩阵表示唯一，邻接表表示不唯一
C. 一个图的邻接矩阵表示不唯一，邻接表表示唯一
D. 一个图的邻接矩阵表示不唯一，邻接表表示不唯一

答案： B

解释：

邻接矩阵的唯一性：邻接矩阵是唯一的，因为它在固定的位置存储了边的信息，行和列对应于顶点，非零元素表示边的存在。
邻接表的非唯一性：邻接表不是唯一的，因为它的构建依赖于读取边的顺序和插入算法。例如，添加边的顺序可能会导致不同的邻接表表示，但表示的图仍然相同。

09. 用邻接表法存储图所用的空间大小()。

选项：

A. 与图的顶点数和边数有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关

答案： A

解释：

邻接表存储图时，顶点数 $ n $ 决定了顶点表的大小，而边数 $ e $ 决定了边表节点的个数。对于无向图，每条边存储两次，因此总的存储空间为 $ O(n + 2e) $。所以，存储空间大小与图的顶点数和边数有关。

10. 若邻接表中有奇数个边表结点，则()

选项：

A. 图中有奇数个结点
B. 图中有偶数个结点
C. 图为无向图
D. 图为有向图

答案： D

解释：

在无向图中，每条边在邻接表中会被存储两次，因此边表节点的个数应该是偶数。如果邻接表中有奇数个边表节点，则说明该图为有向图，并且有奇数条边。

11. 在有向图的邻接表存储结构中，顶点 v 在边表中出现的次数是()

选项：

A. 顶点 v 的度
B. 顶点 v 的出度
C. 顶点 v 的入度
D. 依附于顶点 v 的边数

答案： C

解释：

在有向图的邻接表中，边表存放的是从某个顶点出发的边的信息。顶点 v 在边表中出现的次数即为以顶点 v 为起点的边的数量，也就是顶点 v 的出度。而如果考虑到边的方向，顶点 v 在其他顶点的边表中出现的次数则为顶点 v 的入度。因此，题目中所指的应该是顶点 v 的入度。

12. n个顶点的无向图的邻接表最多有()个边表结点。

选项：

A. $ n $
B. $ n(n-1) $
C. $ n(n+1) $
D. $ n(n-1)/2 $

答案： B

解释：

对于一个无向图，有 $ n $ 个顶点时，最多可以有 $ n(n-1)/2 $ 条边，每条边在邻接表中存储两次，因此边表节点的最大数量为 $ n(n-1) $。

13. 假设有 n 个顶点、e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为()

选项：

A. $ O(n) $
B. $ O(e) $
C. $ O(n + e) $
D. $ O(ne) $

答案： C

解释：

删除与顶点 $ v $ 相关的边包括出边和入边。对于出边，只需遍历顶点 $ v $ 的链表节点及其指向的边表，时间复杂度为 $ O(n) $（最多需要扫描 $ n - 1 $ 个邻接节点）。对于入边，则需遍历整个边表，即扫描剩余的全部顶点表节点及其指向的边表，时间复杂度为 $ O(n + e) $。因此，总的时间复杂度为 $ O(n + e) $。

14. 对邻接表的叙述中，( )是正确的。

选项：

A. 无向图的邻接表中，第 i 个顶点的度为第 i 个链表中节点数的两倍
B. 邻接表比邻接矩阵的操作更简便
C. 邻接矩阵比邻接表的操作更简便
D. 求有向图节点的度，必须遍历整个邻接表

答案： D

解释：

对于无向图，邻接表中第 $ i $ 个顶点的度是第 $ i $ 个链表中的节点数，而不是两倍，因此 A 错误。邻接表和邻接矩阵对于不同的操作各有优势，B 和 C 也不准确。对于有向图，求出度只需遍历与顶点相关的边表，而求入度则需要遍历剩余全部边表，因此 D 正确。

15. 邻接多重表是( )的存储结构。

选项：

A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是

答案： A

解释：

邻接多重表是一种专门用于存储无向图的结构，它能够处理同一对顶点之间的多条边。因此，邻接多重表的存储结构适用于无向图，选 A。

16. 十字链表是()的存储结构。

选项：

A. 无向图
B. 有向图
C. 无向图和有向图
D. 都不是

答案： B

解释：

十字链表是一种用于表示有向图的存储结构。它通过分别存储每个顶点的出边和入边，使得在有向图中查找和操作边更加高效。因此，十字链表的存储结构适用于有向图，选 B。

综合应用题

01，已知带权有向图G的邻接矩阵如下图所示，请画出该带权有向图 G

02.设图 G=(V,E)以邻接表存储，如下图所示。画出其邻接矩阵存储及图G。

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

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

解答：

1) 判别图中有多少条边

无向图：
- 邻接矩阵：边数等于矩阵中 1 的个数除以 2（因为每条边在矩阵中存储两次）。
- 邻接表：边数等于边节点的个数除以 2（每条边在无向图中只存储一次）。
有向图：
- 邻接矩阵：边数等于矩阵中 1 的个数（每条边在矩阵中只存储一次）。
- 邻接表：边数等于边节点的个数（每条边在有向图中只存储一次）。

2) 判别任意两个顶点 $ i $ 和 $ j $ 是否有边相连

无向图或有向图：
- 邻接矩阵：检查矩阵中的元素 $ [i][j] $ 是否为 1。如果为 1，则有边相连；否则，无边相连。
- 邻接表：从顶点表节点 $ i $ 出发，查找编号为 $ j $ 的边表节点。如果找到，表示有边相连；否则，表示无边相连。

3) 任意一个顶点的度是多少？

无向图：
- 邻接矩阵：顶点 $ i $ 的度等于第 $ i $ 行中 1 的个数（即与顶点 $ i $ 相连的边数）。
- 邻接表：顶点 $ i $ 的度等于顶点表节点 $ i $ 的单链表中边表节点的个数。
有向图：
- 邻接矩阵：
  - 顶点 $ i $ 的出度等于第 $ i $ 行中 1 的个数。
  - 顶点 $ i $ 的入度等于第 $ i $ 列中 1 的个数。
  - 顶点 $ i $ 的度数等于出度与入度之和。
- 邻接表：
  - 顶点 $ i $ 的出度等于顶点表节点 $ i $ 的单链表中边表节点的个数。
  - 顶点 $ i $ 的入度等于邻接表中所有编号为 $ i $ 的边表节点的个数。
  - 顶点 $ i $ 的度数等于入度与出度之和。

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

解答：

算法基本思想

设图的顶点分别存储在数组 $ v[n] $ 中。首先初始化邻接矩阵。然后，遍历邻接表，依次遍历顶点 $ v[i] $ 的边链表，并修改邻接矩阵的第 $ i $ 行的元素值。如果链表边节点的值为 $ j $，则置 $ [i][j] = 1 $。遍历完邻接表后，整个转换过程结束。此算法对无向图和有向图均适用。

算法实现

void Convert(ALGraph &G, int arcs[M][N]) {
    // 首先初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            arcs[i][j] = 0; // 初始化为0，表示没有边
        }
    }

    // 依次遍历各顶点表节点为头的边链表
    for (int i = 0; i < n; i++) {
        // 取出顶点 i 的第一条出边
        ArcNode *p = G.v[i].firstarc; // 假设 G.v[i].firstarc 指向边链表的头节点
        
        // 遍历边链表
        while (p != NULL) {
            arcs[i][p->adjvex] = 1; // 如果链表边节点的值为 j，则置 arcs[i][j] = 1
            p = p->nextarc; // 取下一条出边
        }
    }
}

解释

初始化邻接矩阵：首先，创建一个 $ n n $ 的矩阵并将所有元素初始化为 0，表示没有边相连。
遍历邻接表：对于每个顶点 $ i $，从其边链表中取出所有出边节点。如果链表中的边节点的值是 $ j $，则在邻接矩阵中设置 $ [i][j] = 1 $。
处理边链表：通过循环遍历边链表，直到没有更多的边为止，最终构建出完整的邻接矩阵。

此算法有效地将邻接表转换为邻接矩阵，并且对于无向图和有向图都适用。对于无向图，需注意在填充邻接矩阵时可能需要将 $ [j][i] $ 也设为 1，以确保矩阵的对称性。

05. 已知含有5个顶点的图 G，如下图所示。请回答下列问题：

解答：

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

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

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

对于邻接矩阵 $ B $ 的 $ m $ 次幂 $ B^m $，其中 $ B^m $ 中位于 $ i $ 行 $ j $ 列的非零元素表示图中从顶点 $ i $ 到顶点 $ j $ 的长度为 $ m $ 的路径的数量。换句话说，非零元素的值等于从顶点 $ i $ 到顶点 $ j $ 的所有可能路径的数量，且这些路径的长度恰好为 $ m $。

06.【2021统考真题】

已知无向连通图 $ 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) 算法的基本设计思想

本算法的核心思想是基于无向图中顶点的度数性质。对于采用邻接矩阵存储的无向图，非零元素的个数表示该行（或列）对应顶点的度。根据欧拉路径的性质：

如果图中奇数度的顶点个数为 0 或 2，则该图存在 EL 路径。
如果奇数度的顶点个数大于 2，则该图不存在 EL 路径。

因此，算法的步骤为：

遍历邻接矩阵，计算每个顶点的度。
统计度为奇数的顶点个数。
根据奇数度顶点的数量判断是否存在 EL 路径。

2) 算法实现

以下是使用 C 语言实现的算法：

#include <stdio.h>

#define MAXV 100 // 定义最大顶点数

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

// 判断图 G 是否存在 EL 路径的算法
int IsExistEL(MGraph G) {
    int degree, count = 0; // degree: 顶点的度，count: 奇数度顶点计数

    // 遍历所有顶点
    for (int i = 0; i < G.numVertices; i++) {
        degree = 0; // 初始化当前顶点的度

        // 计算顶点 i 的度
        for (int j = 0; j < G.numVertices; j++) {
            degree += G.Edge[i][j]; // 累加邻接矩阵中的非零元素
        }

        // 统计度为奇数的顶点
        if (degree % 2 != 0) {
            count++; // 如果度为奇数，计数器加一
        }
    }

    // 判断奇数度顶点的数量
    if (count == 0 || count == 2) {
        return 1; // 存在 EL 路径
    } else {
        return 0; // 不存在 EL 路径
    }
}

3) 时间复杂度和空间复杂度

时间复杂度:
- 算法需要遍历整个邻接矩阵，因此总的时间复杂度为 $ O(n^2) $，其中 $ n $ 是图中的顶点数。
空间复杂度:
- 由于只使用了有限的额外空间来存储度和计数器，算法的空间复杂度为 $ O(1) $。

数据结构之图的存储

图的存储及基本操作

邻接矩阵法

邻接矩阵的存储结构定义

邻接矩阵的特性

附加性质

邻接表法

1. 结构定义

2. 存储特点

3. 操作效率

4. 入度和出度计算

5. 不唯一性

十字链表

1. 结构定义

2. 十字链表的特性

3. 存储特点

4. 图的示例

图的基本操作

选择题

01. 关于图的存储结构，( )是错误的。

02. 若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则可以断定该图一定( )。

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

04. 带权有向图 G 用邻接矩阵存储，则 v 的入度等于邻接矩阵中( )。

05. 一个有n个顶点的图用邻接矩阵A表示，若图为有向图，顶点v的入度是();若图为无向图，顶点v的度是()

06. 下列哪种图的邻接矩阵是对称矩阵?()

07. 从邻接矩阵 可以看出，该图共有(①)个顶点;若是有向图，则该图共有(②)条弧;若是无向图，则共有(③)条边。

08. 以下关于图的存储结构的叙述中，正确的是()

09. 用邻接表法存储图所用的空间大小()。

10. 若邻接表中有奇数个边表结点，则()

11. 在有向图的邻接表存储结构中，顶点 v 在边表中出现的次数是()

12. n个顶点的无向图的邻接表最多有()个边表结点。

13. 假设有 n 个顶点、e 条边的有向图用邻接表表示，则删除与某个顶点 v 相关的所有边的时间复杂度为()

14. 对邻接表的叙述中，( )是正确的。

15. 邻接多重表是( )的存储结构。

16. 十字链表是()的存储结构。

综合应用题

01，已知带权有向图G的邻接矩阵如下图所示，请画出该带权有向图 G

02.设图 G=(V,E)以邻接表存储，如下图所示。画出其邻接矩阵存储及图G。

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

1) 判别图中有多少条边

2) 判别任意两个顶点 $ i $ 和 $ j $ 是否有边相连

3) 任意一个顶点的度是多少？

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

算法基本思想

算法实现

解释

05. 已知含有5个顶点的图 G，如下图所示。请回答下列问题：

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

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

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

06.【2021统考真题】

1) 算法的基本设计思想

2) 算法实现

3) 时间复杂度和空间复杂度

07. 从邻接矩阵可以看出，该图共有(①)个顶点;若是有向图，则该图共有(②)条弧;若是无向图，则共有(③)条边。