对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。A.O(n)B.O(n²)C.O(e)D.O(eloge)F.O(e²) - 牛搜题

niusouti.com

题目

对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。

A.O(n)

B.O(n²)

C.O(e)

D.O(eloge)

F.O(e²)

相似考题

1.●对于n个顶点e条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为 (24) ，利用Kruskal算法生成最小生成树的时间复杂度为 (25) 。(24) A．O((n+1)2 )B．O(n2 )C．O(n2-1)D．(n2+1)(25) A．O(log2e)B．O(log2e-1)C．O(elog2e)D．以上都不对

2.Prim算法和Kruscal算法都是无向连通网的最小生成树的算法，Prim算法从一个顶点开始，每次从剩余的顶点加入一个顶点，该顶点与当前生成树中的顶占的连边权重最小，直到得到最小生成树开始，Kruscal算法从权重最小的边开始，每次从不在当前的生成树顶点之间的边中选择权重最小的边加入，直到得到一颗最小生成树，这两个算法都采用了（）设计策略，且（）。A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密，则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高

3.什么样的连通图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间复杂度各为多少？它们分别更适合于哪类图？

4.对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。A.完全图B.连通图C.稀疏图D.稠密图

参考答案和解析

参考答案：B,D

更多“对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度(),用Kruskal算法构造最小生成树的时间复杂度为()。 ”相关问题

第1题：

对某个带权连通图构造最小生成树，以下说法中正确的是（）。 Ⅰ.该图的所有最小生成树的总代价一定是唯一的 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.用普里姆（Prim）算法从不同顶点开始构造的所有最小生成树一定相同 Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅲ
D．Ⅳ

有一棵或多棵
第2题：

36、关于最小生成树的求解，下面说法正确的是:
A．求解最小生成树的常用算法有Prim算法，Kruskal算法
B．Kruskal算法每次选择一条最小且不会构成回路权边直至构成一个生成树
C．Prim 算法从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图
D．从算法复杂度的角度看，Kruskal算法适用于稀疏图，Prim算法适用于稠密图

ABC
第3题：

某无向连通图具有n个顶点e条边，利用克鲁斯卡尔算法生成最小生成树的时间复杂度是________。
A．O(elogn)
B．O(eloge)
C．O(nloge)
D．O(ne)

C
第4题：

22、对于n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（）。
A．O(n*n)
B．O(n)
C．O(e)
D．O(nlogn)

正确
第5题：

某无向连通图具有n个顶点e条边，利用普利姆算法生成最小生成树的时间复杂度是________。
A．O(nlogn)
B．O(nloge)
C．O(elogn)
D．O(n^2)

C

相关内容