题目内容
(请给出正确答案)
[单选题]
关于解决最小代价生成树问题的Prim算法的下述说法,不正确的是()。
A.优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重
B.从Q中取出一个顶点的实质是在应用MST性质选择连接A与VA的最小权边
C.算法执行结束后,生成树有n-1个顶点
D.算法以优先队列为空为结束条件
查看答案
如果结果不匹配,请 联系老师 获取答案
A.优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重
B.从Q中取出一个顶点的实质是在应用MST性质选择连接A与VA的最小权边
C.算法执行结束后,生成树有n-1个顶点
D.算法以优先队列为空为结束条件
在一个有n个顶点的带权连通图中,有条边,则应该选用()算法来求这个图的最小生成树,从而使计算时间较少,
A、Prim
B、Kruskal
a)若套用Kruskal或Prim算法构造EMST(G),各需多少时间?
b)试设计一个算法,在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即,在坏情况下,任何此类算法都需要o(nlogn)时间)。
A、图的一棵最小生成树的代价不一定比该图其他任何一棵生成树的代价小
B、带权连通图的最小生成树可能不唯一,但权值最小的边一定出现在解中
C、若带权连通图上各边上的权值互不相同,则该图的最小生成树是唯一的
D、一个带权连通图的最小生成树的权值之和不是唯一的
下面是求无向连通图的最小生成树的一种算法:
//设图中总顶点数为n,总边数为m
将图中所有的边按其权值从大到小排序为;
若图不再连通,则恢复e1;(m=m+1);I=i+1;
(1)试间这个算法是否正确,并说明原因。
(2)以图8-44所示的图为例,写出执行以上算法的过程。