在一个有n个顶点的无向网中，如果边数e小于nlogn，则应该选用Kruskal算法来求这个网的最小生成树，从而使计算时间较少。

在一个有n个顶点的带权连通图中，有条边，则应该选用（)算法来求这个图的最小生成树，从而使计算

在一个有n个顶点的带权连通图中，有条边，则应该选用()算法来求这个图的最小生成树，从而使计算时间较少，

A、Prim

B、Kruskal

如图所示是一个无向网图，请分别按Prim算法和Kruskal算法求最小生成树

A.边稠密连通网

B.边稀疏连通网

C.边稠密无向网

D.边稀疏无向网

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

A．O((n+1)2)

B．O(n2)

C．O(n2-1)

D．(n2+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．以上都不对

Kruskal算法是求权最小的生成树算法，设是一个连通带权图，，则该算法的步骤包括： Step 1: 取，使得. Step 2: 寻找，使得 （1）无环. （2）是满足（1）的具有 的边. Step 3: 如果，停止，否则，令，转步骤2.

算法5-4：最小生成树【图】 Description 最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。 可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。 而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。 在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。 Output 只有一个整数，即最小生成树的总代价。请注意行尾输出换行。 Sample Input4 0 2 4 0 2 0 3 5 4 3 0 1 0 5 1 0Sample Output6

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

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