公司网站空间怎么续费,深圳经济最新新闻,国家大事新闻近三天,网站建设的目标有哪些题目描述
【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统考真题
