下列哪些是常見的最小生成樹算法?()

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

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

A.單源最短路徑中的Dijkstra算法

B.最小生成樹的Prim算法

C.最小生成樹的Kruskal算法

D.計算每對頂點最短路徑的Floyd-Warshall算法

A.Dijkstra算法

B.Kruskal算法

C.Prim算法

D.Floyd算法

E.BFS

A.分數(shù)背包問題

B.Knapsack問題

C.Huffman編碼問題

D.最小生成樹問題

E.DAG的拓撲排序

A.(3，6)

B.(1，3)

C.(1，4)

D.(2，4)

在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為()。

A.O(n)

B.O(n+e)

C.O(n2)

D.O(n3)

A、Kruskal算法

B、Dijkstra算法

C、Floyd算法

D、Prim算法

閱讀下列函數(shù)說明和C代碼，將應填入(n)處的字句寫上。

[說明]

若要在N個城市之間建立通信網絡，只需要N-1條線路即可。如何以最低的經濟代價建設這個網絡，是一個網的最小生成樹的問題?，F(xiàn)要在8個城市間建立通信網絡，其問拓撲結構如圖5-1所示，邊表示城市間通信線路，邊上標示的是建立該線路的代價。

[圖5-1]

無向圖用鄰接矩陣存儲，元素的值為對應的權值?？紤]到鄰接矩陣是對稱的且對角線上元素均為0，故壓縮存儲，只存儲上三角元素(不包括對角線)。

現(xiàn)用Prim算法生成網絡的最小生成樹。由網絡G=(V，E)構造最小生成樹T=(U，TE)的Prim算法的基本思想是：首先從集合V中任取一頂點放入集合U中，然后把所有一個頂點在集合U里、另一個頂點在集合V-U里的邊中，找出權值最小的邊(u，v)，將邊加入TE，并將頂點v加入集合U，重復上述操作直到U=V為止。

函數(shù)中使用的預定義符號如下：

define MAX 32768 /*無窮大權，表示頂點間不連通*/

define MAXVEX 30 /*圖中頂點數(shù)目的最大值*/

typedef struct{

int startVex，stopVex; /*邊的起點和終點*/

float weight; /*邊的權*/

}Edge;

typedef struct{

char vexs[MAXVEX]; /*頂點信息*/

float arcs[MAXVEX*(MAXVEX-1)/2]; /*鄰接矩陣信息，壓縮存儲*/

int n; /*圖的頂點個數(shù)*/

}Graph;

[函數(shù)]

void PrimMST(Graph*pGraph, Edge mst[])

{

int i,j,k,min,vx,vy;

float weight，minWeight;

Edge edge;

for(i=0; i＜pGraph-＞n-1；i++){

mst[i].StartVex=0;

mst[i].StopVex=i+1;

mst[i].weight=pGraph-＞arcs[i];

}

for(i=0；i＜(1)；i++){/*共n-1條邊*/

minWeight=(float)MAX;

min=i;

/*從所有邊(vx，vy)中選出最短的邊*/

for(j=i; j＜pGraph-＞n-1; j++){

if(mst[j].weight＜minWeight){

minWeight=(2);

min=j；

}

}

/*mst[minl是最短的邊(vx，vy)，將mst[min]加入最小生成樹*/

edge=mst[min]；

mst[min]=mst[i];

mst[i]=edge;

vx=(3);/*vx為剛加入最小生成樹的頂點下標*/

/*調整mst[i+1]到mst[n-1]*/

for(j=i+1；j＜pGraph-＞n-1；j++){

vy=mst[j].StopVex;

if((4) ){/*計算(vx，vy)對應的邊在壓縮矩陣中的下標*/

k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1；

}else{

k=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;

}

weight(5)；

if(weight＜mst[j].weight){

mst[j].weight=weight;

mst[j].StartVex=vx;

}

}

}

}

(1)

程分為若于階段，每一階段選取若干條邊.算法思路如下：

(1)將每個頂點視為一棵樹，圖中所有頂點形成一個森林;

(2)為每棵樹選取一條邊，它是該樹與其他樹相連的所有邊中權值最小的一條邊，把該邊加入生成樹中。如果某棵樹選取的邊已經被其他樹選過，則該邊不再選取。

重復以上操作，直到整個森林變成一棵樹。

以圖8-44所示的圖為例，寫出執(zhí)行以上算法的過程。