首页 > 软考
题目内容 (请给出正确答案)
[主观题]

Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一 个顶点开始,每次从剩余的

顶点加入一个顶点,该顶点与当前生成树中的顶占的连边权重 最小,直到得到最小生成树开始,Kruscal算法从权重最小的边开始,每次从不在当前的生成树顶点之间的边中选择权重最小的边加入,直到得到一颗最小生成树,这两个算法都采用了()设计策略,且()。

A.分治 B.贪心 C.动态规划 D.回溯 A.若网较稠密,则Prim算法更好 B.两个算法得到的最小生成树是一样的 C.Prim算法比Kruscal算法效率更高 D.Kruscal算法比Prim算法效率更高

查看答案
答案
收藏
如果结果不匹配,请 联系老师 获取答案
您可能会需要:
您的账号:,可能还需要:
您的账号:
发送账号密码至手机
发送
安装优题宝APP,拍照搜题省时又省心!
更多“Prim算法和Kruscal算法都是无向连通网的最小生成树的…”相关的问题
第1题
已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点,试画出构

已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点,试画出构造过程)。

已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点,试画【哈尔滨工业大学2000九(8分)】

点击查看答案
第2题
对于n个顶点e条边的无向连通图,利用Prim算法生成最小生成树的时间复杂度为(24),利用Kruskal算法

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

A.O((n+1)2)

B.O(n2)

C.O(n2-1)

D.(n2+1)

点击查看答案
第3题
Prim算法是一种动态规划算法。()
点击查看答案
第4题
最小生成树的构造可使用()。

A.prim算法

B.冒泡算法

C.迪杰斯特拉算法

D.哈夫曼算法

点击查看答案
第5题
求稠密图的最小生成树,最好用Prim算法。()
点击查看答案
第6题
在图G中求两个结点之间的最短路径可以采用的算法是()。

A.迪杰斯特拉(Dijkstra)算法

B.克鲁斯卡尔(Kruskal)算法

C.普里姆(Prim)算法

D.广度优先遍历(BFS)算法

点击查看答案
第7题
若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。(1)如果图
若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。(1)如果图

若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。

(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥,将把图分割成两个连通分量。

(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法,判断连通图G中是否有桥,若有。输出这样的桥。

点击查看答案
第8题
利用“有向无环图中极大顶点入度必为零”的性质,实现一个拓扑排序算法,若输入为有向无环图则给出拓扑排序,否则报告“非有向无环图”。该算法时间、空间复杂度各是多少?

点击查看答案
第9题
对于如下图所示的带权无向图,用图示说明:利用Kruskal算法构造最小生成树的过程。

对于如下图所示的带权无向图,用图示说明:利用Kruskal算法构造最小生成树的过程。请帮忙给出正确答

点击查看答案
第10题
下面()算法可用于求无向图的所有连通分量。
下面()算法可用于求无向图的所有连通分量。

A、广度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

点击查看答案
退出 登录/注册
发送账号至手机
密码将被重置
获取验证码
发送
温馨提示
该问题答案仅针对搜题卡用户开放,请点击购买搜题卡。
马上购买搜题卡
我已购买搜题卡, 登录账号 继续查看答案
重置密码
确认修改