拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题图中无向边上

问答题

简答题

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

请回答下列问题。
（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。
（2）题图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。
（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？

【参考答案】

1）为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动prim算法或kruskal算法作图。注意本题最小生成树有两种构造，如下图所示。

方案的总费用为16。
2）存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用Prim算法（或kruskal算法）。
3）TTL=5，即IP分组的生存时间（最大传递距离）为5，方案1中TL和BJ的距离过远，TTL=5不足以让IP分组从H1传送到H2，因此H2不能收到IP分组。而方案2中TL和BJ邻近，H2可以收到IP分组。