[项目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条边，该图至少有多少个顶点? (要求写出计算过程)
2. 已知带权有向图G 的邻接矩阵如下图所示，请画出该带权有向图G。
| 0 | 15 | 2 | 12 | ∞ | ∞ | ∞ |
| ∞ | 2 | ∞ | ∞ | 6 | ∞ | ∞ |
| ∞ | ∞ | 0 | ∞ | 8 | 4 | ∞ |
| ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 3 |
| ∞ | ∞ | ∞ | ∞ | 0 | ∞ | 9 |
| ∞ | ∞ | ∞ | 5 | ∞ | 0 | 10 |
| ∞ | 4 | ∞ | ∞ | ∞ | ∞ | 0 |
3. 对下图所示无向图，按照Dijkstra算法，写出从顶点1到其他各个顶点的最短路径和最短路径长度。 🏷️Img_Pro1102
提示：使用表格法给出Dijkstra算法求解步骤
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小题，建议使用表格法依次计算出
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分组？
【选做题】[奖励分：0~1]
下图所示为一个用AOE网表示的工程。 🏷️Img_Pro1103
1）画出此图的邻接表表示
2）完成工程至少需要多少时间
3）指出关键路径
4）哪些活动加速可以缩短完成工程所需的时间?
【扩展练习】
1. 已知有向图如下图所示。 🏷️Img_Pro1114
1）写出该图的邻接矩阵表示并据此给出从顶点1出发的深度优先遍历序列（要求按顶点序号从小达大进行遍历）。
2）求该有向图的强连通分量的数量。
3）给出该图的任意两个拓扑序列。
4）若将改图视为无向图，分别用Prim算法和Kruskal算法求最小生成树。
2.【2011统考真题】已知有6个顶点（顶点编号为0~5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
| 4 | 6 | ∞ | ∞ | ∞ | 5 | ∞ | ∞ | ∞ | 4 | 3 | ∞ | ∞ | 3 | 3 |
要求：
1）画出图G的邻接矩阵 A。
2）画出有向带权图 G。
3）求图G的关键路径，并计算该关键路径的长度。
提示：在构建上三角矩阵的时候，通常需要包含主对角线，但数据结构中的图结构通常都是简单图，这就意味着不存在自回路，相应的主对角线的值即为默认的固定值。
3.【2017统考真题】使用Prim算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题：
1）对下列图G（🏷️Img_Pro1106），从顶点A开始求G的MST，依次给出按算法选出的边。
2）图G的MST是唯一的吗？
3）对任意的带权连通图，满足什么条件时，其MST是唯一的吗？