题目内容
(请给出正确答案)
[主观题]
考查某些边的权重不是正数的带权网络。试证明:a)对此类网络仍可以定义最小支撑树——此时,Prim算法是否依然可行?b)若不含负权重环路,则仍可以定义最短路径树——此时,Dijkstra算法是否依然可行?
查看答案
如果结果不匹配,请 联系老师 获取答案
A、实数
B、正整数
C、正数
D、非负数
设f(x)在[0,1]上连续,在(0,1)内可导,且f(0)=0,f(1)=1,试证:对于任意给定的正数a,b,在(0,1)内存在不同的使
A.优先队列Q中顶点的键值指这个顶点与A集合中点的最小权边的权重
B.从Q中取出一个顶点的实质是在应用MST性质选择连接A与VA的最小权边
C.算法执行结束后,生成树有n-1个顶点
D.算法以优先队列为空为结束条件
a)若套用Kruskal或Prim算法构造EMST(G),各需多少时间?
b)试设计一个算法,在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即,在坏情况下,任何此类算法都需要o(nlogn)时间)。
在一个有n个顶点的带权连通图中,有条边,则应该选用()算法来求这个图的最小生成树,从而使计算时间较少,
A、Prim
B、Kruskal
点是否在同一个连通分量上,在该算法中选择权值最小的边的原则是该边不能在图中构成(②),它主要适用于(③)。
A、稀疏
B、稠密
C、完全
D、不完全