在Prim算法中,假设当前U集合为{v1, v3, v6},V-U集合为{v2, v4, v5},且已知lowcost数组为[0, 5, 0, 6, 8, 4],adjvex数组为[0, v3, 0, v3, v3, v3]。请问下一步应该将哪个顶点加入U集合?
答案解析
核心考点说明:Prim算法中如何选择下一个加入U集合的顶点。解题思路分析:根据Prim算法的原理,每次选择V-U集合中到U集合距离最近的顶点加入U集合。具体到本题,需要查看lowcost数组,找到V-U集合中对应顶点的最小lowcost值。每个选项的详细分析:A. v2的lowcost为5,不是最小值;B. v4的lowcost为6,不是最小值;C. v5的lowcost为8,不是最小值;D. v6的lowcost为4,是最小值。易错点提醒:注意lowcost数组中0表示该顶点已经在U集合中,不应被选择。
正确答案:D