违法和不良信息举报 联系客服
免费注册 登录

对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。

题目
对(),用Prim算法求最小生成树较为合适,而Kruskal算法适于构造()图的最小生成树。

A.完全图

B.连通图

C.稀疏图

D.稠密图

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

请分别用Prim算法和Kruskal算法构造以下网络的最小生成树，并求出该树的代价。


(1)用Prim算法构造最小生成树： ①n=8，只有顶点V 0 在最小生成树中。 mst[7]={{0，1，2}，{0，2，3}，{0，3，∞}，{0，4，∞}，{0，5，∞}，{0，6，∞}，{0，7，∞}} 这里的mst[]中每个元素{i，j，w}对应图中权为w的一条边。 ②在mst[0]到mst[6]找出权值最小的边mst[0]，即(V 0 ，V 1 )，将顶点V 1 及边加入到最小生成树中。 ③调整mst[1]到mst[6]，得到 mst[7]={{0，1，2}，{0，2，3}，{1，3，2}，{0，4，∞}，{0，5，∞}，{0，6，∞}，{0，7，∞}} 这里的黑体{0，1，2}表示该元素对应的边已经在最小生成树中。 ④在mst[1]到mst[6]找出权值最小的边mst[2]，即(V 1 ，V 3 )，将顶点V 3 及边加入到最小生成树中。 ⑤调整mst[2]到mst[6]，得到 mst[7]={{0，1，2}，{1，3，2}，{3，2，1)，{3，4，2}，{3，5，4}，{0，6，∞}，{0，7，∞}} 得到的最小生成树如下图所示： (2)用Kruskal算法构造最小生成树 集合E中按权递增顺序排列为：(V 2 ，V 3 )，(V 4 ，V 5 )，(V 5 ，V 7 )，(V 6 ，V 7 )，(V 0 ，V 1 )，(V 1 ，V 3 )，(V 3 ，V 4 )，(V 4 ，V 6 )，(V 5 ，V 6 )，(V 0 ，V 2 )，(V 3 ，V 5 )。 ①初始时，最小生成树为只有7个顶点的非连通图。 ②边(V 2 ，V 3 )的两个顶点分别属于两个连通分量，将边(V 2 ，V 3 )加入到最小生成树中。 ③同理，将边(V 4 ，V 5 )，(V 5 ，V 7 )，(V 6 ，V 7 )，(V 0 ，V 1 )，(V 1 ，V 3 )，(V 3 ，V 4 )加入到最小生成树中。 得到的最小生成树如下图所示：

第2题：

7、下面（）算法适合构造一个稠密图G的最小生成树。

A．Prim算法

B．Kruskal算法

C．Floyd算法

D．Dijkstra算法


A

第3题：

下面（）适合构造一个稠密图G的最小生成树。

A．Prim算法

B．Kruskal算法

C．Floyd算法

D．Dijkstra算法


A

第4题：

36、关于最小生成树的求解，下面说法正确的是:

A．求解最小生成树的常用算法有Prim算法，Kruskal算法

B．Kruskal算法每次选择一条最小且不会构成回路权边直至构成一个生成树

C．Prim 算法从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图

D．从算法复杂度的角度看，Kruskal算法适用于稀疏图，Prim算法适用于稠密图


ABC

第5题：

下列（）算法适合构造一个稠密图G的最小生成树。

A．Prim算法

B．Kruskal算法

C．Floyd算法

D．Dijkstra算法


Prim算法

第6题：

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


错误

第7题：

下面()算法适合构造一个稠密图G的最小生成树。

A.Prim算法

B、Kruskal算法

C.Floyd算法

D、Dijkstra算法


参考答案：A
解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。

第8题：

对稀疏图,用 Prim算法求最小生成树较为合适。()

此题为判断题(对，错)。


正确答案：错

第9题：

对________,用 Prim算法求最小生成树较为合适。

A、非连通图

B、连通图

C、稀疏图

D、稠密图


正确答案：D

相关内容