题5

题5

题目

Q:用 Prim 算法求一个带权连通图的最小生成树, 在算法执行的某个时刻, 已选取的顶点集合 ,已选取的边集合 ,要选取下一条权值最小的边, 应当从 ( ) 组中选取.
A.
B.
C.
D.

分析

A:选择的是，可以和顶点集合连通，同时边权最小的边。
TE中的元素，比如其中第一个元素1代表的是顶点1，第二个元素2代表的是顶点2，所以表示的是顶点1和顶点2之间的边。
选取下一条权值最小的边，应当从顶点集合U中的顶点和顶点集合V-U中的顶点之间的边中选择。其中V是指所有的顶点集合。

解

A
,候选边只能是这两个顶点集之间的边,只有 符合题意。
也就是只能是左边U出第一个元素，右边的V-U出第二个元素，构成边，这样的话就是从已知的点，连通到下一个未知的点，将其纳入最小生成树