免费下载素材的设计网站,怎么做卖车网站,汕头市手机网站建设品牌,微信小程序怎么一键删除题目描述
【2015统考真题】求下面的带权图的最小#xff08;代价#xff09;生成树时#xff0c;可能是Kruskal算法第2次选中但不是Prim算法#xff08;从v4开始#xff09;第2次选中的边是#xff08;C#xff09; A. (V1, V3) B. (V1, V4) C. (V2, V3) D. (V3, V4) …题目描述
【2015统考真题】求下面的带权图的最小代价生成树时可能是Kruskal算法第2次选中但不是Prim算法从v4开始第2次选中的边是C A. (V1, V3) B. (V1, V4) C. (V2, V3) D. (V3, V4)
解析 Kruskal 算法步骤 第一次选中边 (V1, V4, 5)第二次可选的边有 (V1, V3, 8)、(V3, V4, 8)、(V2, V3, 8) Prim 算法步骤 用一个 dist 数组记录其他顶点到 V n e w V_{new} Vnew 的距离dist[i] 表示节点 i 到 V n e w V_{new} Vnew初始时 V n e w V_{new} Vnew 没有元素 d i s t [ i ] ∞ dist[i] \infty dist[i]∞题目规定从 V4 出发 d i s t [ 4 ] 0 dist[4] 0 dist[4]0第一次选中的边是 (V1, V4, 5)
参考文献
[1] prim算法 [2] kruskal算法 [3] 2015年408统考真题
