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