🏷️ 知识点：割性质

用 Prim 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的顶点集合 U={1,2,3}，已选取的边集合 TE={(1,2),(2,3)}，要选取下一条权值最小的边，应当从（　　）组中选取。

A. {(1,4),(3,4),(3,5),(2,5)} B. {(3,4),(3,5),(4,5),(1,4)} C. {(1,2),(2,3),(3,5)} D. {(4,5),(1,3),(3,5)}

[tag_link]

正确答案：A

结论

选 A。

推导

Prim 的候选边必须横跨割 (U, V−U)，即一端在 {1,2,3}、另一端在未加入顶点集合。只有 A 中的边全部满足该条件；然后从 A 的候选边中选权值最小者。

易错点

已选边 TE 不能再次作为候选；连接 U 内两个顶点的边会形成内部边，不属于 Prim 当前割边集合。