在Prim算法中,若当前U集合为{v1, v3, v6, v4},V-U集合为{v2, v5},且已知lowcost数组为[0, 5, 0, 0, 8, 0],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已经在U集合中,不应被选择;C. v5的lowcost为8,不是最小值;D. v6已经在U集合中,不应被选择。易错点提醒:注意lowcost数组中0表示该顶点已经在U集合中,不应被选择。
正确答案:A
随机推荐
开始刷题