题目内容
(请给出正确答案)
[主观题]
求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中______的数目正相关。
求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中______的数目正相关。
查看答案
如果结果不匹配,请 联系老师 获取答案
求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中______的数目正相关。
A.边稠密,边稀疏
B.边稀疏,边稠密
C.边稠密,边稠密
D.边稀疏,边稀疏
在一个有n个顶点的带权连通图中,有条边,则应该选用()算法来求这个图的最小生成树,从而使计算时间较少,
A、Prim
B、Kruskal
已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点,试画出构造过程)。
【哈尔滨工业大学2000九(8分)】
点是否在同一个连通分量上,在该算法中选择权值最小的边的原则是该边不能在图中构成(②),它主要适用于(③)。
A、稀疏
B、稠密
C、完全
D、不完全
在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()。
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
a)若套用Kruskal或Prim算法构造EMST(G),各需多少时间?
b)试设计一个算法,在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即,在坏情况下,任何此类算法都需要o(nlogn)时间)。