题目

拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光缆的铺设费用。

请回答下列问题：

(1) 仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。

(2) 题 42 图可采用图的哪一种存储结构？给出求解问题 (1) 所使用的算法名称。

(3) 假设每个城市采用一个路由器按 (1) 中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL = 5 的 IP 分组，则 H2 是否可以收到该 IP 分组？

解析

(1) 最经济的光缆铺设方案

答案：共有 2 种最经济方案，总费用都是 16。

MST 求解过程——8 个城市需 7 条边连通，按 Kruskal 思路把所有边按权值升序处理：

权 2 边（5 条，全选）	权 3 边（5 条，选 2 条）	权 4 边（2 条，不选）
XA-BJ, XA-WH, TL-JN, QD-JN, QD-NJ	BJ-TL, BJ-WH, WH-QD, JN-NJ, CS-QD	BJ-JN, WH-CS

5 条权 2 边全部选——它们彼此不形成环，分别构成两个连通块和一个孤立点：

• 块 1：{XA, BJ, WH}（由 XA-BJ + XA-WH 构成）
• 块 2：{TL, JN, QD, NJ}（由 TL-JN + QD-JN + QD-NJ 构成）
• 块 3：{CS}（孤立）

还需 2 条权 3 边连接 3 个块：

• CS 只能通过 CS-QD 连入块 2（其他权 3 边都不沾 CS）→ CS-QD 必选；
• 块 1 与块 2 之间，权 3 候选有 BJ-TL 和 WH-QD，选其一即可（BJ-WH 是块 1 内部、JN-NJ 是块 2 内部，跳过）。

得到两种 MST：

方案	选用边集	费用
方案 A	XA-BJ, XA-WH, TL-JN, QD-JN, QD-NJ, BJ-TL, CS-QD	2×5 + 3×2 = 16
方案 B	XA-BJ, XA-WH, TL-JN, QD-JN, QD-NJ, WH-QD, CS-QD	2×5 + 3×2 = 16

(2) 存储结构与算法名称

答案：邻接表（顶点稀疏图）；算法可用 Kruskal 或 Prim。

• 存储结构：图有 8 个顶点 12 条边，属于稀疏图——每个顶点平均度只有 3。邻接矩阵需 个单元，邻接表只需存 24 个边端（每条边存 2 次），更省空间。
• 算法：求 MST 标准两选——Kruskal（按边排序 + 并查集，适合稀疏图）或 Prim（按顶点扩展 + 优先队列，适合稠密图）。本题边数少，Kruskal 更直观。

(3) H1 → H2 的 IP 分组能否到达？

答案：

• 若组网采用方案 A（含 BJ-TL 直连）：H2 能收到；
• 若组网采用方案 B（含 WH-QD 但没有 BJ-TL）：H2 收不到。

逐方案分析路径与 TTL 消耗——TTL 规则：每经过一个路由器先减 1，若减到 0 立刻丢弃，不再转发。

方案 A——TL 与 BJ 直连：

途经路由器仅 2 个。TTL 变化：5 → 4（TL 转发） → 3（BJ 投递给 H2 本地）。包顺利到达，H2 接收，TTL=3。

方案 B——无 TL-BJ 边，TL 到 BJ 必须绕路：

途经路由器 6 个。TTL 变化：5 → 4 → 3 → 2 → 1 → 0（XA 处）。XA 把 TTL 减到 0，丢弃，BJ 永远收不到，H2 也收不到。

编者注（生僻术语）：本题为数据结构与计算机网络综合题——前两问考 MST，第三问考 IP 协议的 TTL 字段。TTL（Time To Live）的"每跳减 1、到 0 丢弃"是网络层基础，目的是防止环路下数据包永久转发。考研做这种综合题先把图建准，路径数清楚，再对照 TTL 算就稳了。