[项目011] 图的的综合应用 隐藏答案 | 返回首页
作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。
最后更新：2023年12月16日
作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。
【课后作业】
1. 图 G 是一个非连通无向图，共有28条边，该图至少有多少个顶点? (要求写出计算过程)
答案及解析：
由于图G是一个非联通图，当边数固定时，顶点最少的情况应该是由1个顶点和一个完全图构成。此时，完全图的结点数n可以通过公式 e=n(n-1)/2=28求解获得，即n=8；总结点数=8+1=9个。
2. 已知带权有向图G 的邻接矩阵如下图所示，请画出该带权有向图G。
| 0 | 15 | 2 | 12 | ∞ | ∞ | ∞ |
| ∞ | 0 | ∞ | ∞ | 6 | ∞ | ∞ |
| ∞ | ∞ | 0 | ∞ | 8 | 4 | ∞ |
| ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 3 |
| ∞ | ∞ | ∞ | ∞ | 0 | ∞ | 9 |
| ∞ | ∞ | ∞ | 5 | ∞ | 0 | 10 |
| ∞ | 4 | ∞ | ∞ | ∞ | ∞ | 0 |
答案及解析：
首先为邻接矩阵补上结点编号，然后根据邻接矩阵绘制出带权有向图G，如下图所示。🏷️Img_Pro1101
3. 对下图所示无向图，按照Dijkstra算法，写出从顶点1到其他各个顶点的最短路径和最短路径长度。 🏷️Img_Pro1102
提示：使用表格法给出Dijkstra算法求解步骤
答案及解析：
| S | d[1], path[1] | d[2], path[2] | d[3], path[3] | d[4], path[4] | d[5], path[5] | d[6], path[6] |
|---|---|---|---|---|---|---|
| {1} | 0, -1 | 7, 1 | 11, 1 | ∞, -1 | ∞, -1 | ∞, -1 |
| {1,2} | 0, -1 | 7, 1 | 11, 1 | 16, 2 | ∞, -1 | ∞, -1 |
| {1,2,3} | 0, -1 | 7, 1 | 11, 1 | 16, 2 | 18, 3 | 19, 3 |
| {1,2,3,4} | 0, -1 | 7, 1 | 11, 1 | 16, 2 | 18, 3 | 19, 3 |
| {1,2,3,4,5} | 0, -1 | 7, 1 | 11, 1 | 16, 2 | 18, 3 | 19, 3 |
| {1,2,3,4,5,6} | 0, -1 | 7, 1 | 11, 1 | 16, 2 | 18, 3 | 19, 3 |
| 路径 | - | 1,2 | 1,3 | 1,2,4 | 1,3,5 | 1,3,6 |
| 长度 | - | 7 | 11 | 16 | 18 | 19 |
4. 下表给出了某工程各工序之间的优先关系和各工序所需的时间（其中“-”表示无先驱工序），请完成以下各题：
1）画出相应的AOE网
2）列出各事件的最早发生时间和最迟发生时间
3）求出关键路径并指明完成该工程所需的最短时间
| 工序代号 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
| 所需时间 | 3 | 2 | 2 | 3 | 4 | 3 | 2 | 1 |
| 先序工序 | - | - | A | A | B | A | C、E | D |
提示：
- 本题中的工序（A~H）代表的是AOE图中的活动，即结点之间的弧，绘制AOE网时，需要根据活动间的先后关系自行构建结点。
- 第2-3小题，建议使用表格法依次计算出
答案及解析：
1）画出相应的AOE网
根据题意绘制AOE网 🏷️Img_Pro1104，注意本题中的工序表示的是AOE网的边。
2）列出各事件的最早发生时间和最迟发生时间
| v1 | v2 | v3 | v4 | v5 | v6 | |
|---|---|---|---|---|---|---|
| 0 | 3 | 2 | 6 | 6 | 8 | |
| 0 | 4 | 2 | 6 | 7 | 8 |
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| weight | 3 | 2 | 2 | 3 | 4 | 3 | 2 | 1 |
| 0 | 0 | 3 | 3 | 2 | 3 | 6 | 6 | |
| 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 | |
| 时间余量 | 1 | 0 | 1 | 1 | 0 | 2 | 0 | 1 |
| 关键活动 | - | Y | - | - | Y | - | Y | - |
3）求出关键字并指明完成该工程所需的最短时间
关键路径：B, E, G
最短时间=关键路径长度= 2+4+2 = 8。
5.【2018统考真题】拟建设一个光通信骨干网络连通BJ，CS，XA，QD，JN，NJ，TL和WH等8个城市，下图中无向边上的权值表示两个城市之间备选光缆的铺设费用。请回答下列问题： 🏷️Img_Pro1107
1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。
2）该图可采用图的哪种存储结构？给出求解问题1）所用的算法名称。
3）假设每个城市采用一个路由器按1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？
答案及解析：
1）使用Kruskal算法获取生成树，总共有2种不同的生成树，其长度（总费用）= 2×5+3×2 = 16。
🏷️Img_Pro1107
2）该图可采用图的邻接矩阵或邻接表进行存储。构造最小生成树可以使用Kruskal算法或Prim算法。
3）假设每个城市采用一个路由器按1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？
TTL=5表示IP分组的生存时间为5。方案一中，TL和BJ距离为3，可以实现IP分组的接受；在方案二中，TL和BJ的最小距离为11，超出了TTL的值，因此无法收到IP分组。
【选做题】[奖励分：0~1]
下图所示为一个用AOE网表示的工程。 🏷️Img_Pro1103
1）画出此图的邻接表表示
2）完成工程至少需要多少时间
3）指出关键路径
4）哪些活动加速可以缩短完成工程所需的时间?
答案及解析：
1）画出此图的邻接表表示 🏷️Img_Pro1103AdjacencyList
2）完成工程至少需要多少时间
3）指出关键路径
| v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 2 | 5 | 5 | 6 | 8 | 12 | 12 | 16 | |
| 0 | 3 | 5 | 7 | 6 | 9 | 12 | 14 | 16 |
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | a13 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| weight | 2 | 5 | 5 | 3 | 3 | 1 | 3 | 2 | 6 | 4 | 3 | 4 | 2 |
| 0 | 0 | 0 | 2 | 2 | 5 | 5 | 5 | 6 | 8 | 8 | 12 | 12 | |
| 1 | 0 | 1 | 4 | 3 | 5 | 6 | 7 | 6 | 10 | 9 | 12 | 14 | |
| 时间余量 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | 2 | 0 | 2 | 1 | 0 | 2 |
| 关键活动 | - | Y | - | - | - | Y | - | - | Y | - | - | Y | - |
由上表可得：
关键路径：a2, a6, a9, a12
两条路径的长度为：5+1+6+4=16。
4）哪些活动加速可以缩短完成工程所需的时间?
加速活动a2, a6, a9, a12可以缩短工程所需的时间。
【扩展练习】
1. 已知有向图如下图所示。 🏷️Img_Pro1114
1）写出该图的邻接矩阵表示并据此给出从顶点1出发的深度优先遍历序列（要求按顶点序号从小达大进行遍历）。
2）求该有向图的强连通分量的数量。
3）给出该图的任意两个拓扑序列。
4）若将改图视为无向图，分别用Prim算法和Kruskal算法求最小生成树。
答案及解析：
1）计算邻接矩阵和深度优先遍历序列
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 3 | 6 | - | - | - |
| 2 | - | 0 | 4 | - | 5 | - | - |
| 3 | - | - | 0 | - | 4 | - | - |
| 4 | - | - | - | 0 | - | 5 | - |
| 5 | - | - | - | - | 0 | - | 3 |
| 6 | - | - | 3 | - | - | 0 | 7 |
| 7 | - | - | - | - | - | - | 0 |
根据邻接矩阵可以获得深度优先遍历序列：1,2,3,5,7,4,6。
2）计算强连通分类的数量
基本思路：当某个顶点只存在出度，而不存在入度时，该顶点将成为一个孤立点，即单独构成一个强连通分量。此时可以先将入度为0的点作为单独的强连通分量，然后删除该点和以该点位为起点的边，然后再去判断剩余的图是否还存在独立的连通分量，并依次进行计数和删除。最终剩下的图将做为最后一个强连通分量。根据这个原则，我们可以依次获得独立的强连通分量点1,2,4,6,3,5,7。即，总共7个强连通分量。
3）本题只存在2个拓扑序列，分别是：1246357，1426357
4）使用Prim算法获得生成树的序列为：1-2, 1-3, 3-6, 3-5, 5-7, 6-4
🏷️Img_Pro1114SpanningTree
2.【2011统考真题】已知有6个顶点（顶点编号为0~5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
| 4 | 6 | ∞ | ∞ | ∞ | 5 | ∞ | ∞ | ∞ | 4 | 3 | ∞ | ∞ | 3 | 3 |
要求：
1）画出图G的邻接矩阵 A。
2）画出有向带权图 G。
3）求图G的关键路径，并计算该关键路径的长度。
提示：在构建上三角矩阵的时候，通常需要包含主对角线，但数据结构中的图结构通常都是简单图，这就意味着不存在自回路，相应的主对角线的值即为默认的固定值。
答案及解析：
1）画出图G的邻接矩阵 A。
根据上三角矩阵规则，可以将一维数组转换为如下邻接矩阵:
2）画出有向带权图 G 🏷️Img_Pro1105
3）求图G的关键路径，并计算该关键路径的长度。
本题图比较简单，可以直接写出关键路径0->1->2->3->5。大家可以根据关键路径的推导方法，使用表格法进行验证。🏷️Img_Pro1105Path
关键路径长度 = 4+5+4+3 = 16
3.【2017统考真题】使用Prim算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题：
1）对下列图G（🏷️Img_Pro1106），从顶点A开始求G的MST，依次给出按算法选出的边。
2）图G的MST是唯一的吗？
3）对任意的带权连通图，满足什么条件时，其MST是唯一的吗？
答案及解析：
1）根据Prim算法，每次从已确定的生成树T中选择一个权重最小的边加入生成树，因此步骤如下：
第1趟，T中顶点为A，候选边(A,B), (A,D), (A,E)，选择(A,D)加入；
第2趟，T中顶点为A,D，侯选边(A,B), (A,E), (D,C), (D,E)，选择(D,E)加入；
第3趟，T中顶点为A,D,E，侯选边(A,B), (D,C), (C,E)，选择(C,E)加入；
第4趟，T中顶点为A,D,E,C，侯选边(A,B), (C,B)，选择(C,B)加入；
T即为最小生成树，依次选出的边为：(A,D),(D,E),(E,C),(C,B)。
2）使用Prim算法构建的图G的MST是唯一的。因为，选入最小生成树的边都是原图中权重最小的边。其中，边(A,E)和(E,C)具有相同的权重，若用(A,E)替换(E,C)则会产生环，因此1）中选出生成树是唯一的。
3）对任意的带权连通图，满足什么条件时，其MST是唯一的吗？
当带权连通图的任意一个环中所包含的边的权值均不相同时，MST是唯一的。因为对于不同权值的环，始终可以选出权重最小的一条边，加入生成树。