用Prim算法求一个连通的带权图的最小生成树,在算法执行的某时刻,已选取的顶点集合U={1,2,3},已选取的边的集合TE={(1,2),(2,3)},要选取下一条权值最小的边,应当从______ 组边中选取。
A. {(1,4),(3,4),(3,5),(2,5)}
B. {(4,5),(1,3),(3,5)}
C. {(1,2),(2,3),(3,5)}
D. {(3,4),(3,5),(4,5),(1,4)}
只能从已选择顶点出发
Prim算法是一种用于求解带权连通图的最小生成树的算法。在算法执行的过程中,我们从一个顶点开始,然后每次选择一条连接已选取的顶点集合U和未选取的顶点集合的权值最小的边,将这条边以及它的另一个顶点加入到U和TE中。
在这个问题中,已选取的顶点集合U={1,2,3},已选取的边的集合TE={(1,2),(2,3)}。我们需要从连接集合U和未选取的顶点集合的边中选取权值最小的边。
选项A:{(1,4),(3,4),(3,5),(2,5)} 这组边都是连接已选取的顶点集合U和未选取的顶点集合的,因此我们可以从这组边中选取权值最小的边。
选项B:{(4,5),(1,3),(3,5)} 边(4,5)和边(1,3)不是连接已选取的顶点集合U和未选取的顶点集合的,因此我们不能从这组边中选取权值最小的边。
选项C:{(1,2),(2,3),(3,5)} 边(1,2)和边(2,3)已经被选取,因此我们不能从这组边中选取权值最小的边。
选项D:{(3,4),(3,5),(4,5),(1,4)} 边(4,5)不是连接已选取的顶点集合U和未选取的顶点集合的,因此我们不能从这组边中选取权值最小的边。
所以,我们应当从选项A中选取下一条权值最小的边。这是因为选项A中的所有边都是连接已选取的顶点集合U和未选取的顶点集合的。在Prim算法中,我们总是选择连接已选取的顶点集合U和未选取的顶点集合的权值最小的边。因此,正确答案是选项A。
谁能解释一下
xiaoqin 回复 xiaoqin: 明白了
A
用户登录可进行刷题及查看答案
登录后提交答案