大连免费网站制作,团队建设思路和方案,寺庙网站开发,网络运营公司的经营范围题目描述
【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统考真题
