最小生成樹論文

1、精選文檔最小生成樹最小生成樹問題摘要：本文通過對最小生成樹兩種算法（Kruskal算法和Prim算法）的分析，用C語言寫出了Kruskal算法的C語言源程序，通過計(jì)算機(jī)實(shí)現(xiàn)求一個(gè)連通圖的最小生成樹問題。關(guān)鍵詞：最小生成樹 Kruskal算法 Prim算法 C語言源程序引言 現(xiàn)實(shí)中一些實(shí)際應(yīng)用問題可通過利用連通圖、生成樹的模型來建立求解，找出最優(yōu)的方法，而在任意一個(gè)連通圖中存在很多條生成樹，如何從這些生成樹中找出一條權(quán)最小的生成樹對解決現(xiàn)實(shí)生活中實(shí)際應(yīng)用問題具有重大意義，所以經(jīng)過數(shù)學(xué)家的爭辯，目前最小生成樹的算法主要有Kruskal算法和Prim算法，那么對這兩種方法在計(jì)算機(jī)上的實(shí)現(xiàn)也關(guān)系著效率

2、的提高，兩種算法的C語言程序也應(yīng)運(yùn)而出。正文一 對最小生成樹問題中的生疏: G(V，E)是一個(gè)樹，若p(G)2，則G中至少有兩個(gè)懸掛點(diǎn)。 樹G(V，E)中不相鄰的兩個(gè)點(diǎn)間添上一條邊，則得到只含一個(gè)圈的圖G'；若在圖G'中從該圈中再去掉任意一條邊得到圖G"，則圖G"又成為樹。二 最小生成樹的算法： Kruskal算法（避圈法）： 令i=1，E0=(空集)； 選一條eiEEi-1,使ei是全部不在Ei-1中且與Ei-1不構(gòu)成圈的邊中權(quán)最小的邊，假如這樣的邊不存在，算法終止，此時(shí)Ei-1=m-1,則T=（V，Ei-1）是最小樹；若Ei-1<m-1，則說明原圖

3、G=（V,E）不是連通的。 令Ei= Ei-1ei，ii+1，轉(zhuǎn)步。定理：G=(V,E)是連通圖，則上述Kruskal算法肯定有限終止，且終止時(shí)得到的子圖T肯定是圖G的最小生成樹。 Prim算法： 從任意一個(gè)節(jié)點(diǎn)i開頭，找到離節(jié)點(diǎn)i最近的節(jié)點(diǎn)j。令V1=i,j，E1=( i,j),稱V1的節(jié)點(diǎn)為連通節(jié)點(diǎn)集合，網(wǎng)絡(luò)中其余的節(jié)點(diǎn)V1'=VVi稱作非聯(lián)通節(jié)點(diǎn)集。E1=( i,j)將在最小生成樹中。令k=1. 若Vk'=,算法終止，已找到最小生成樹，Vk為相應(yīng)的節(jié)點(diǎn)集，Ek為相應(yīng)的邊集；否則從Vk'中選擇一個(gè)離Vk最近的成員節(jié)點(diǎn)p（假如Vk'中有兩個(gè)或兩個(gè)以上的節(jié)點(diǎn)離V

4、k最近，則從中選一個(gè)；假如Vk'中全部節(jié)點(diǎn)均不能與Vk連通，則說明圖G不是連通的）。設(shè)q是表示Vk中離p最近的節(jié)點(diǎn)，則邊（p,q）將在最小生成樹中。更新Vk和 Vk'，令Vk+1Vkp, Vk+1'Vk'p,Ek+1Ek(p,q)。 令k=k+1，轉(zhuǎn)步。三 C語言源程序：#include <stdio.h>#include <stdlib.h> #define MAX 100#define MAXCOST 0x7fffffff int graphMAXMAX; int Prim(int graphMAX, int n)/* lowcost

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

6、1 = 0; /* n個(gè)節(jié)點(diǎn)至少需要n-1條邊構(gòu)成最小生成樹 */for (i = 2; i <= n; i+)min = MAXCOST;minid = 0; /* 找滿足條件的最小權(quán)值邊的節(jié)點(diǎn)minid */for (j = 2; j <= n; j+)/* 邊權(quán)值較小且不在生成樹中 */if (lowcostj < min && lowcostj != 0)min = lowcostj;minid = j;/* 輸誕生成樹邊的信息:起點(diǎn)，終點(diǎn)，權(quán)值 */printf("%c - %c : %dn", mstminid + 'A

7、' - 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ā)覺更小的權(quán)值 */if (graphminidj < lowcostj)/* 更新權(quán)值信息 */lowcostj = graphminidj; /* 更新最小權(quán)值邊的起點(diǎn) */mstj = minid;/* 返回最小權(quán)值和 */return sum; int main()int

8、i, j, k, m, n;int x, y, cost;char chx, chy; /* 讀取節(jié)點(diǎn)和邊的數(shù)目 */printf("輸入連通圖的節(jié)點(diǎn)和邊的數(shù)目:n");scanf("%d%d", &m, &n);getchar(); /* 初始化圖，全部節(jié)點(diǎn)間距離為無窮大 */for (i = 1; i <= m; i+)for (j = 1; j <= m; j+)graphij = MAXCOST; /* 讀取邊信息 */for (k = 0; k < n; k+)printf("輸入第%d條邊的信息:&

9、quot;,k+1);scanf("%c %c %d", &chx, &chy, &cost);getchar();i = chx - 'A' + 1;j = chy - 'A' + 1;graphij = cost;graphji = cost; /* 求解最小生成樹 */printf("最小生成樹為:n");cost = Prim(graph, m); /* 輸出最小權(quán)值和 */printf("最小權(quán)值和為:%dn", cost); /system("pause");return 0;四 C程序解題：編寫程序:對于如下一個(gè)帶權(quán)無向圖，給出節(jié)點(diǎn)個(gè)數(shù)以及全部邊權(quán)值，用Kruskal算法求最小生成樹。輸入數(shù)據(jù):7 11A B 7A D 5B C 8B D 9B E 7C E 5D E 15D F 6E F 8E G 9F G 11運(yùn)行結(jié)果為：結(jié)論：最小生成樹的兩種算法各有各的優(yōu)點(diǎn)，要視具體問題打算使用哪種方法解決問題，但本質(zhì)上都是選擇加入當(dāng)前剩余邊集中最短的邊，被成為“貪欲”算法；將數(shù)學(xué)方法和計(jì)算機(jī)語言結(jié)合起來將極大提高解題的效率，通過這種形式既加深了對最小生成樹算