2. 计算机
  3. 现在拟建造一个连接11个城市的铁路网络，要求任何2个城市或者直接可达或者间接可达。用每个结点表示一个城市，2个结点之间边的权值表示2个城市之间直达铁路的造价，由此可得如图5-3所示的各城市之间的造价图。若要求设计的铁路网络总造价最小，则这个最小造价为(1)

现在拟建造一个连接11个城市的铁路网络，要求任何2个城市或者直接可达或者间接可达。用每个结点表示一个城市，2个结点之间边的权值表示2个城市之间直达铁路的造价，由此可得如图5-3所示的各城市之间的造价图。若要求设计的铁路网络总造价最小，则这个最小造价为(1)

admin2007-10-08  43
问题 现在拟建造一个连接11个城市的铁路网络，要求任何2个城市或者直接可达或者间接可达。用每个结点表示一个城市，2个结点之间边的权值表示2个城市之间直达铁路的造价，由此可得如图5-3所示的各城市之间的造价图。若要求设计的铁路网络总造价最小，则这个最小造价为(1)。这个问题相当于求解已知图的(2)。
选项 A、266
B、268
C、271
D、273
答案A
解析 显然，这是求已知图的最小生成树的问题。含有n个顶点的连通图的生成树有n个顶点和n-1条边。对一个带权的图(网)，在一棵生成树中，各条边的权植之和称为这棵生成树的代价。其中代价最小的生成树称为最小代价生成树(简称最小生成树)。
   MST性质：设G=(V,E)是一个连通网络，U是顶点集V的一个真子集。若(u,v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u,v)。
   求连通的带权无向图的最小代价生成树的算法有普里姆(Prim)算法和克鲁斯卡尔 (Kruskal)算法。
   (1)普里姆算法
   设已知G=(V,E)是一个带权连通无向图，顶点V={0，1，2，...，n-1}。设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时U只包含一个出发顶点。设 T是构造生成树过程中已被考虑在生成树上的边的集合，初始时T为空。如果边(i,j)具有最小代价，且i∈U,j∈V-U，那么最小代价生成树应包含边(i,j)。把j加到U中，把 (i,j)加到T中。重复上述过程，直到U等于V为止。这时，T即为所求的最小代价生成树的边的集合。
   普里姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普里姆算法的时间复杂度为O(n2)，与图中边数无关，所以适合于稠密图。
   (2)克鲁斯卡尔算法
   设T的初始状态是只有n个顶点而无边的森林，按边长递增的顺序选择
   
E中的n-1安全边(u,v)并加入T，生成最小生成树。所谓安全边是指2个端点分别是森林T里2棵树中的顶点的边。加入安全边，可将森林中的2棵树连接成一棵更大的树，因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的 T是一棵最小生成树。
   克鲁斯卡尔算法的特点是当前形成的集合T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O(elog2e)，与图中顶点数无关，所以适合于稀疏图。
   本题使用普里姆算法构造最小生成树的过程如图5-4所示。
   根据图5-4，则最小造价为25+35+55+20+20+12+45+23+10+21=266。
转载请注明原文地址:https://kaotiyun.com/show/JdQZ777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)