最小耗費(fèi)生成樹Prim算法實(shí)驗(yàn)報(bào)告講解

1、済 int Prim( int graph MAX, int n) /* lowcosti 記錄以 i 為終點(diǎn)的邊的最小權(quán)值，當(dāng) lowcosti=0 時(shí)表示終點(diǎn) i 加入生成樹 */ int lowcost MAX; /* msti 記錄對(duì)應(yīng) lowcosti 的起點(diǎn)，當(dāng) msti=0 時(shí)表示起點(diǎn) i 加入生成樹 */ int mst MAX; int i, j, min, minid, sum = 0; /* 默認(rèn)選擇 1號(hào)節(jié)點(diǎn)加入生成樹，從 2號(hào)節(jié)點(diǎn)開始初始化 */ for (i = 2; i = n; i+) /* 最短距離初始化為其他節(jié)點(diǎn)到 1號(hào)節(jié)點(diǎn)的距離 */ lowcosti =

2、 graph1i; /* 標(biāo)記所有節(jié)點(diǎn)的起點(diǎn)皆為默認(rèn)的 1號(hào)節(jié)點(diǎn) */ msti = 1; /* 標(biāo)記 1號(hào)節(jié)點(diǎn)加入生成樹 */ mst1 = 0; /* n 個(gè)節(jié)點(diǎn)至少需要 n-1 條邊構(gòu)成最小生成樹 */ for (i = 2; i = n; i+) min = MAXCOS; T minid = 0; /* 找滿足條件的最小權(quán)值邊的節(jié)點(diǎn) minid */ for (j = 2; j =n; j+) /* 邊權(quán)值較小且不在生成樹中 */ if (lowcostj min minid = j; /* 輸出生成樹邊的信息 : 起點(diǎn)，終點(diǎn)，權(quán)值 */ printf( %c - %c : %dn

3、, mstminid +A - 1, minid + A - 1, min); /* 累加權(quán)值 */ sum += min; /* 標(biāo)記節(jié)點(diǎn) minid 加入生成樹 */ lowcostminid = 0; /* 更新當(dāng)前節(jié)點(diǎn) minid 到其他節(jié)點(diǎn)的權(quán)值 */ for (j = 2; j =n; j+) /* 發(fā)現(xiàn)更小的權(quán)值 */ if ( graph minidj lowcostj) /* 更新權(quán)值信息 */ lowcostj = graph minidj; /* 更新最小權(quán)值邊的起點(diǎn) */ mstj = minid; /* 返回最小權(quán)值和 */ return sum; int main(

4、) printf( 請(qǐng)輸入點(diǎn)數(shù)和邊數(shù)： ); int i, j, k, m, n; int x, y, cost; char chx, chy; scanf( %d%d, /* 讀取節(jié)點(diǎn)和邊的數(shù)目 */ getchar(); printf( 請(qǐng)輸入邊的信息： ); /* 初始化圖，所有節(jié)點(diǎn)間距離為無(wú)窮大 */ for (i = 1; i = m; i+) for (j = 1; j = m; j+) graphij =MAXCOS; T /* 讀取邊信息 */ for (k = 0; k n; k+) scanf( %c %c %d, getchar(); i = chx - A + 1; j

5、 = chy - A + 1; graphij = cost; graphji = cost; /* 求解最小生成樹 */ cost = Prim(graph, m); /* 輸出最小權(quán)值和 */ printf( Total:%dn , cost); /system(pause); return 0; 代碼說(shuō)明： 1、2個(gè)for循環(huán)都是從2開始的，因?yàn)橐话阄覀兡J(rèn)開始就把第一個(gè)節(jié)點(diǎn)加入生成 樹，因此之后不需要再次尋找它。 2、lowcosti記錄的是以節(jié)點(diǎn)i為終點(diǎn)的最小邊權(quán)值。初始化時(shí)因?yàn)槟J(rèn)把第一個(gè)節(jié) 點(diǎn)加入生成樹，因此 lowcosti = graph1i ，即最小邊權(quán)值就是各節(jié)點(diǎn)到 1

6、號(hào)節(jié)點(diǎn) 的邊權(quán)值。 3、msti記錄的是lowcosti對(duì)應(yīng)的起點(diǎn)，這樣有起點(diǎn)，有終點(diǎn)，即可唯一確定一條 邊了。初始化時(shí) msti = 1，即每條邊都是從 1 號(hào)節(jié)點(diǎn)出發(fā)。 編寫程序 :對(duì)于如下一個(gè)帶權(quán)無(wú)向圖，給出節(jié)點(diǎn)個(gè)數(shù)以及所有邊權(quán)值，用 Prim 算法 求最小生成樹。 三、結(jié)論 1 、實(shí)驗(yàn)結(jié)果 輸入數(shù)據(jù): 7 11 A B 7 A D 5 B C 8 B D 9 B E 7 C E 5 D E 15 D F 6 E F 8 F G 11 輸出: A - D : 5 D - F : 6 A - B : 7 B - E : 7 E - C : 5 E - G : 9 Total:39 實(shí)驗(yàn)結(jié)果

7、如圖: 02109 I I I I I IGGFFEEEDCD GCEBFD1986157985 J 15曠嚴(yán) 9 57 7 6 5氐洽 C:w5-dow$sy$-em32cmd.exe GGFFEEEDCD竦 1986157985 15曠 A C:w5-dcsy$-em32cmd.exe X 2、分析討論 Prim算法的基本思想如下： 首先從V中任取一個(gè)頂點(diǎn)（假定取v1）,將生成樹T置為僅有一 個(gè)結(jié)點(diǎn)v1的樹，即U=v1;然后只要U是V的真子集，就在所有那些一個(gè)端點(diǎn)在 T中，另一個(gè) 端點(diǎn)在T外的邊中，找一條最短（即權(quán)值最小 ）的邊。假定符合條件的最短邊為 （vi,vj）, 則把 該條邊和其不在 T中的頂點(diǎn)vj，分別并入T的邊集TE和頂點(diǎn)集U。如此進(jìn)行下去，每