算法和Kruskal算法求最小生成树的时间各为多少？它们分别适合于哪类图？

下面哪些使用的不是贪心算法()

A.单源最短路径中的Dijkstra算法

B.最小生成树的Prim算法

C.最小生成树的Kruskal算法

D.计算每对顶点最短路径的Floyd-Warshall算法

●对于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．以上都不对

在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)

程分为若于阶段，每一阶段选取若干条边.算法思路如下：

(1)将每个顶点视为一棵树，图中所有顶点形成一个森林;

(2)为每棵树选取一条边，它是该树与其他树相连的所有边中权值最小的一条边，把该边加入生成树中。如果某棵树选取的边已经被其他树选过，则该边不再选取。

重复以上操作，直到整个森林变成一棵树。

以图8-44所示的图为例，写出执行以上算法的过程。

A.(3，6)

B.(1，3)

C.(1，4)

D.(2，4)

下面是求无向连通图的最小生成树的一种算法：

//设图中总顶点数为n，总边数为m

将图中所有的边按其权值从大到小排序为;

若图不再连通，则恢复e₁;(m=m+1);I=i+1;

(1)试间这个算法是否正确，并说明原因。

(2)以图8-44所示的图为例，写出执行以上算法的过程。

A、Kruskal算法

B、Dijkstra算法

C、Floyd算法

D、Prim算法