最小生成樹求解課程設(shè)計(jì)報(bào)告

1、<p><b>　　計(jì)算機(jī)科學(xué)與技術(shù)系</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2009～2010 學(xué)年 第 二 學(xué)期</p><p><b>　　2010年 6月</b></p><p><b>　　課程設(shè)計(jì)題目&l

2、t;/b></p><p>　　對(duì)任意給定的網(wǎng)和起點(diǎn)，用PRIM算法的基本思想求解出所有的最小生成樹。</p><p><b>　　問題分析和任務(wù)定義</b></p><p>　　本課程設(shè)計(jì)重在使用prim算法實(shí)現(xiàn)任意給定的網(wǎng)和起點(diǎn)的圖的所有最小生成樹的求解，實(shí)現(xiàn)本課程設(shè)計(jì)的關(guān)鍵即是能夠掌握prim算法的思想，并能夠靈活使用。</p

3、><p>　　首先我們必須對(duì)prim算法有個(gè)清晰地認(rèn)識(shí)，prim算法是普利姆（Prime）于1957年提出了一種構(gòu)造最小生成樹的算法，算法的主要思想如下：按照將頂點(diǎn)逐個(gè)連通的步驟，把頂點(diǎn)加入到已經(jīng)連通的頂點(diǎn)集合U中，最后使得U成為最小生成樹。</p><p>　　PRIM思路：1）初始化頂點(diǎn)集合U為空集。</p><p>　　2）任意選取一個(gè)頂點(diǎn)v加入U(xiǎn)。</p&

4、gt;<p>　　3）選取一條權(quán)值最小的邊（u,v），其中u∈U，v∈（V-U），將該邊假如到生成樹，v加入到U中。</p><p>　　4）重復(fù)步驟3），直到所有頂點(diǎn)均加入到U中構(gòu)成一顆最小生成樹。</p><p>　　為了實(shí)現(xiàn)這一算法需要附設(shè)一個(gè)輔助數(shù)組closedge[v]用來存儲(chǔ)從U到V-U之間具有最小代價(jià)的邊。對(duì)于每個(gè)頂點(diǎn) v∈（V-U），在closedge，樹組中

5、都存在一個(gè)分量closedge[v]，它有兩個(gè)域組成。其中一個(gè)是權(quán)值，即：</p><p>　　closedge[v].lowcost=MIN{cost（u,v）|u∈U}，另外一個(gè)是頂點(diǎn)域vexs，存儲(chǔ)依附于該邊在U中的頂點(diǎn)。 </p><p>　　其次，針對(duì)本課程設(shè)計(jì)的題目要求，我們需要考慮到五個(gè)問題：</p><p>　　如何選擇、設(shè)計(jì)一個(gè)合適的算法來建立圖，

6、用以實(shí)現(xiàn)接下來的操作。</p><p>　　如何正確的在本實(shí)驗(yàn)中使用prim算法。</p><p>　　對(duì)于本課程設(shè)計(jì)中的需要，求出對(duì)于給定任意給定的網(wǎng)和結(jié)點(diǎn)，得出所有的最小生成樹，關(guān)鍵在于需要求出所有的最小生成樹，需要靈活使用prim算法實(shí)現(xiàn)。</p><p>　　對(duì)于一些細(xì)節(jié)也是需要考慮斟酌的，比如，當(dāng)所輸入的頂點(diǎn)不存在時(shí)，需要一個(gè)示語句警示，并能夠重新輸入。&

7、lt;/p><p>　　當(dāng)算法設(shè)計(jì)完成后，還需對(duì)于整個(gè)運(yùn)行程序的運(yùn)行界面，提示語句以及如何完美、清楚的輸出各個(gè)最小生成樹設(shè)計(jì)一番。</p><p>　　最后，在課程設(shè)計(jì)過程中，自己需要做好充足的準(zhǔn)備工作，吃透課本中關(guān)于prim算法的解釋說明，同時(shí)把握好時(shí)間，掌握整個(gè)課程設(shè)計(jì)的進(jìn)度，做好整體規(guī)劃，保證本次課程設(shè)計(jì)可以及時(shí)的、成功的設(shè)計(jì)出來。</p><p>　　數(shù)據(jù)結(jié)構(gòu)的

8、選擇和概要設(shè)計(jì)</p><p>　　對(duì)于本次設(shè)計(jì)，在prim算法中使用的圖均為無向圖，對(duì)于各頂點(diǎn)之間的權(quán)值以及連通關(guān)系是采用鄰接矩陣來實(shí)現(xiàn)的。同時(shí)在prim算法中采用了輔助數(shù)組closedge[v]，主要用來存儲(chǔ)到頂點(diǎn)的最小邊權(quán)值。</p><p>　　建立圖的數(shù)據(jù)結(jié)構(gòu)類型如下：</p><p>　　typedef struct{</p><p&

9、gt;　　int vexs[MAX]; //頂點(diǎn)信息集合</p><p>　　int arcs[MAX][MAX]; //各邊的權(quán)值</p><p>　　int vexnum; //頂點(diǎn)數(shù)</p><p>　　int arcnum; //邊數(shù)</p><p>　　}MGraph

10、; //圖類型</p><p>　　建立輔助數(shù)組結(jié)構(gòu)類型如下：</p><p>　　struct closed{</p><p>　　int adjvex; //依附于最小權(quán)值邊在頂點(diǎn)集合U中的頂點(diǎn)</p><p>　　int lowcost; //存儲(chǔ)最小邊的權(quán)值</p><p

11、><b>　　};</b></p><p>　　closed closedge[MAX];</p><p>　　整個(gè)算法概要設(shè)計(jì)主要在于圖的初始化，以及如何求出所有最小生成樹。下面我們可以通過相應(yīng)的流程圖來清楚的理解。</p><p>　　剛開始時(shí)初始化各頂點(diǎn)的頂點(diǎn)域、權(quán)值域賦值的算法流程:</p><p><

12、;b>　　j不等于I</b></p><p><b>　　j等于I</b></p><p><b>　　小于等于</b></p><p><b>　　大于</b></p><p>　　.求出最小代價(jià)的邊的算法流程:</p><p>&l

13、t;b>　　小于</b></p><p><b>　　大于等于</b></p><p>　　有一個(gè)條件不滿足 都是肯定的回答</p><p><b>　　是</b></p><p><b>　　否</b></p&g

14、t;<p>　　對(duì)于上述流程圖可簡單解釋如下，首先通過對(duì)其它頂點(diǎn)依次判斷，找出相連的頂點(diǎn)，然后得到頂點(diǎn)序號(hào)，再通過for循環(huán)，進(jìn)行循環(huán)判斷，找出邊權(quán)值最小的，并賦值進(jìn)入closedge[]中。</p><p>　　重新調(diào)整各頂點(diǎn)中的頂點(diǎn)域和權(quán)值域的流程:</p><p><b>　　有一個(gè)不滿足</b></p><p><b

15、>　　答案是肯定的</b></p><p><b>　　是的</b></p><p><b>　　否</b></p><p>　　普利姆算法的總流程:</p><p><b>　　是</b></p><p><b>　　否&

16、lt;/b></p><p>　　圖3-7. 普利姆算法的總流程圖</p><p><b>　　主函數(shù)的流程：</b></p><p><b>　　詳細(xì)設(shè)計(jì)和編碼</b></p><p><b>　　圖的建立：</b></p><p>　　MGra

17、ph CreateMarph(MGraph &G){</p><p>　　int v1,v2,weight,i,j,k;</p><p>　　printf("●●請(qǐng)輸入無向圖的頂點(diǎn)數(shù)和邊數(shù)：");</p><p>　　scanf("%d%d",&G.vexnum,&G.arcnum);</p>

18、;<p>　　for(i=0;i<G.vexnum;i++){ //初始化鄰接矩陣</p><p>　　for(j=0;j<G.vexnum;j++){</p><p>　　G.arcs[i][j]=0;</p><p><b>　　}}</b></p><p>　　for(i=0

19、;i<G.vexnum;i++){</p><p>　　printf("第%d個(gè)頂點(diǎn)的序號(hào)：",i+1);</p><p>　　scanf("%d",&G.vexs[i]);</p><p><b>　　}</b></p><p>　　printf("\n-

20、--------------請(qǐng)你確定各條弧的信息--------------\n");</p><p>　　for(k=0;k<G.arcnum;k++)</p><p>　　{printf("●●請(qǐng)輸入第%d弧的兩個(gè)起始頂點(diǎn)和其權(quán)值為：",k+1);//輸入一條邊及依附的頂點(diǎn)及權(quán)值</p><p><b>　　for(

21、; ;){</b></p><p>　　scanf("%d%d%d",&v1,&v2,&weight);</p><p>　　if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum))</p><p>&l

22、t;b>　　break;</b></p><p><b>　　else</b></p><p>　　printf("輸入有誤，不存在該頂點(diǎn)，請(qǐng)重新輸入^_^\n");</p><p><b>　　}</b></p><p>　　i=LocateVex(G.vex

23、s,v1); //找到兩個(gè)結(jié)點(diǎn)在鄰接矩陣中的位置</p><p>　　j=LocateVex(G.vexs,v2);</p><p>　　G.arcs[i][j]=weight; //邊的權(quán)值</p><p>　　G.arcs[j][i]=G.arcs[i][j]; //置(v1,v2)成

24、(v2,v1)</p><p><b>　　}</b></p><p>　　printf("-----------------------------------------------\n");</p><p><b>　　return G;</b></p><p><b

25、>　　}</b></p><p>　　本子函數(shù)是用來建立圖，其中用到了鄰接矩陣用以存儲(chǔ)各邊的權(quán)值以及判斷是否連通，</p><p>　　其中所調(diào)用的LocateVex()是用來指出該頂點(diǎn)在鄰接矩陣中所在的位置，其子函數(shù)定義如下：int LocateVex(int vexs[],int v){ //確定結(jié)點(diǎn)是否存在</p><p><b>

26、;　　int t;</b></p><p>　　for(int i=0;i<MAX;i++)</p><p>　　if(vexs[i]==v)</p><p><b>　　t=i;</b></p><p><b>　　return t;</b></p><p&g

27、t;<b>　　}</b></p><p>　　使用Prim算法實(shí)現(xiàn)找出圖中的最小生成樹</p><p>　　void MiniTree_PRIM(MGraph G,int u){</p><p><b>　　int k=u;</b></p><p><b>　　int i,j;</

28、b></p><p>　　for(i=0;i<G.vexnum;i++) //初始化closedge數(shù)組，v={u}</p><p>　　if(i!=k) //兩個(gè)頂點(diǎn)不重合</p><p>　　{closedge[i].adjvex=u+1; //首先將u視為第一條邊的第一個(gè)依附頂點(diǎn)</p><p&g

29、t;　　if(!G.arcs[k][i]) //兩點(diǎn)之間不連通</p><p>　　closedge[i].lowcost=-1;</p><p><b>　　else</b></p><p>　　closedge[i].lowcost=G.arcs[k][i]; //調(diào)整closedge數(shù)組的最小代價(jià)lowcost為邊上的

30、權(quán)值</p><p><b>　　}</b></p><p>　　closedge[k].lowcost=0;</p><p>　　for(i=0;i<G.vexnum-1;i++) { //★取其余G.vexnum-1個(gè)頂點(diǎn)，循環(huán)從此處開始，i無任何意義</p><p>　　for(j=0

31、;j<G.vexnum;j++)</p><p>　　if(closedge[j].lowcost>0){ //求出T的下一個(gè)結(jié)點(diǎn)，第K結(jié)點(diǎn)</p><p><b>　　k=j;</b></p><p><b>　　break;}</b></p><p>　　fo

32、r(j=0;j<G.vexnum;j++)</p><p>　　if(closedge[j].lowcost>0)</p><p>　　if(closedge[j].lowcost<closedge[k].lowcost) //比較權(quán)值大小,從中找出權(quán)值最小的邊</p><p><b>　　k=j;</b></p>

33、;<p>　　printf(" %d -----------------> %d ( %d )\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);</p><p>　　closedge[k].lowcost=0; //將此第k個(gè)頂點(diǎn)并入U(xiǎn)集中</p><p>　　f

34、or(j=0;j<G.vexnum;j++) ////在頂點(diǎn)k并入U(xiǎn)之后， 更新closedge[i]，新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊</p><p>　　if(G.arcs[k][j]>0){ </p><p>　　if(closedge[j].lowcost==-1){ //如果先前時(shí)此兩個(gè)頂點(diǎn)之間是不連通的</p&g

35、t;<p>　　closedge[j].lowcost=G.arcs[k][j]; //新的權(quán)值域改成新加入頂點(diǎn)與該頂點(diǎn)的權(quán)值</p><p>　　closedge[j].adjvex=G.vexs[k];}</p><p>　　else //如果此前兩頂點(diǎn)本已連通</p><p>　　if(G

36、.arcs[k][j]<closedge[j].lowcost){ //調(diào)整closedge數(shù)組中各邊的最小權(quán)值</p><p>　　closedge[j].adjvex=G.vexs[k]; //依附于最小權(quán)值邊在U中的頂點(diǎn)</p><p>　　closedge[j].lowcost=G.arcs[k][j]; //邊的權(quán)值賦給closedge數(shù)組的最小權(quán)值域</p&g

37、t;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}}</b></p><p>　　其中要說明的是其中使用了一個(gè)輔助數(shù)組，其定義如下：</p><p>　　struct closed{</p>&

38、lt;p>　　int adjvex; //依附于最小權(quán)值邊在頂點(diǎn)集合U中的頂點(diǎn)</p><p>　　int lowcost; //存儲(chǔ)最小邊的權(quán)值</p><p><b>　　};</b></p><p>　　此數(shù)組對(duì)PRIM中產(chǎn)生的頂點(diǎn)和邊的權(quán)值進(jìn)行臨時(shí)存儲(chǔ)的數(shù)組，因此結(jié)構(gòu)體中設(shè)計(jì)兩個(gè)變量，頂點(diǎn)名adjvex，邊的權(quán)值lo

39、wcost。定義次數(shù)組名為closed closedge[MAX]</p><p>　　在用PRIM算法計(jì)算圖的最小生成樹過程中，這里是整個(gè)算法的核心之所在。先要指定點(diǎn)u最為最小生成樹的起點(diǎn)，并以次來構(gòu)成最小生成樹，子函數(shù)中用k來作為u的載體，同時(shí)它也是u在圖中的位置，后對(duì)輔助數(shù)組closedge進(jìn)行初始化，首先將u視為第一條邊的第一個(gè)依附頂點(diǎn)，從零開始，所以u(píng)+1。如果兩點(diǎn)間不連通則給邊的權(quán)值lowcost賦值

40、-1；否則將選擇的邊的權(quán)值adj賦給loecost，即將起存儲(chǔ)在輔助數(shù)組中。而后開始尋找下一個(gè)結(jié)點(diǎn)，進(jìn)行邊的權(quán)值的比較，選擇出最小權(quán)值的邊。將該邊的頂點(diǎn)和權(quán)值存儲(chǔ)入輔助數(shù)組中，然后重新選擇最小邊，如此重復(fù)直至結(jié)束。將在次過程中選擇的邊的頂點(diǎn)和權(quán)值全部存儲(chǔ)進(jìn)輔助數(shù)組中。而后開始調(diào)整輔助數(shù)組中各個(gè)邊的最小權(quán)值，在輔助數(shù)組中生成最小生成樹。最后將存儲(chǔ)在輔助數(shù)組中的最小生成樹輸出。其中，使用多個(gè)FOR的套嵌來實(shí)現(xiàn)最小權(quán)值邊的選擇。數(shù)組在這過程中

41、始終作為臨時(shí)存儲(chǔ)空間，將篩選出的邊的信息存儲(chǔ)著，最后將其輸出來。</p><p>　　可建立由五點(diǎn)構(gòu)建的圖如下： </p><p>　　普利姆算法中closedge數(shù)組的變化</p><p>　　最后以頂點(diǎn)1開始所生成的最小生成樹如下：</p><p><b>　　上機(jī)調(diào)試</b></p><p>

42、;　　通過調(diào)試分析，發(fā)現(xiàn)此程序中的closedge數(shù)組變化是一個(gè)難點(diǎn)，其中的數(shù)值變化時(shí)整個(gè)課程設(shè)計(jì)的關(guān)鍵，或多或少有點(diǎn)繁瑣，不容易掌握清楚。</p><p>　　對(duì)一些特殊情況沒有考慮到，從而造成本設(shè)計(jì)出來的程序不全面，如在輸入圖中頂點(diǎn)信息時(shí)，沒有考慮到輸入的頂點(diǎn)不存在的情況。</p><p>　　如果數(shù)據(jù)之間的類型不同，會(huì)引發(fā)數(shù)據(jù)間交換紊亂。指針空間未分配而導(dǎo)致系統(tǒng)隨機(jī)給出個(gè)錯(cuò)誤數(shù)據(jù)。地

43、址相沖突導(dǎo)致的程序錯(cuò)誤。這些都沒有語法錯(cuò)誤但是在調(diào)試中將引起亂碼，是個(gè)重要的問題，而且會(huì)頻繁出現(xiàn)。因此要多調(diào)試，思考以解決這些問題。</p><p>　　在尋找下一結(jié)點(diǎn)時(shí)，尋找到最小權(quán)值邊，將其兩端的頂點(diǎn)信息及變的權(quán)值存儲(chǔ)到輔助樹組中。在設(shè)計(jì)解決這些問題的時(shí)候用多個(gè)for進(jìn)行套嵌實(shí)現(xiàn)查找、判斷。因?yàn)楸境绦蚴褂玫氖莗rim算法，for循環(huán)的使用套嵌較復(fù)雜，因此在設(shè)計(jì)時(shí)要理清思路。</p><p&

44、gt;<b>　　時(shí)間、空間性能分析</b></p><p>　　根據(jù)程序中的循環(huán)語句可以判斷出普利姆算法的時(shí)間復(fù)雜度為O(n2)。算法和圖中邊的數(shù)目無關(guān)，因此普利姆算法適合于求稠密網(wǎng)的最小生成樹。因?yàn)樵谒惴ㄖ羞\(yùn)用了鄰接矩陣的存儲(chǔ)結(jié)構(gòu)，在無向圖中，鄰接矩陣是對(duì)稱的。所以僅需要存儲(chǔ)上三角(下三角)的元素，因此需要n(n+1)個(gè)存儲(chǔ)空間。</p><p><b>

45、;　　測試結(jié)果和分析</b></p><p>　　對(duì)于上圖測試結(jié)果如下所示：</p><p><b>　　用戶使用說明</b></p><p>　　本程序是在Microsoft Visual C++環(huán)境下運(yùn)行，經(jīng)過本人調(diào)試運(yùn)行成功。運(yùn)行過程時(shí)帶有提示性語句。由于是求解圖的最小生成樹，因此先進(jìn)行圖的頂點(diǎn)數(shù)和邊數(shù)的輸入。然后對(duì)各個(gè)頂點(diǎn)進(jìn)

46、行頂點(diǎn)信息的輸入。接著對(duì)各個(gè)邊的起點(diǎn)、終點(diǎn)、權(quán)值進(jìn)行輸入。在其過程中若輸入不存在的頂點(diǎn)時(shí)會(huì)有語句提示，并且重新輸入。然后是選擇是否輸出所建圖的的鄰接矩陣，若輸入有錯(cuò)誤時(shí)會(huì)有提示語句，并重新選擇。最后輸出的是按各頂點(diǎn)為起點(diǎn)輸出所有的最小生成樹。</p><p><b>　　參考文件</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法》 王昆侖，李紅主編 中國鐵道出版社，2

47、007年6月第一版</p><p>　　《C程序設(shè)計(jì)》 譚浩強(qiáng)主編 清華大學(xué)出版社 2006.11</p><p>　　《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程》 徐孝凱主編 清華大學(xué)出版社 2004</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》 胡學(xué)鋼主編 高等教育出版社 2006</p><p>　　網(wǎng)絡(luò)搜索 www.baidu.com&

48、lt;/p><p><b>　　附錄（源程序）</b></p><p>　　#include"stdio.h"</p><p>　　#include"stdlib.h"</p><p>　　#include"malloc.h"</p><p>

49、;　　#define MAX 20</p><p>　　typedef struct{</p><p>　　int vexs[MAX]; //頂點(diǎn)信息集合</p><p>　　int arcs[MAX][MAX]; //各邊的權(quán)值</p><p>　　int vexnum; //頂點(diǎn)數(shù)</p&

50、gt;<p>　　int arcnum; //邊數(shù)</p><p><b>　　}MGraph;</b></p><p>　　int LocateVex(int vexs[],int v){ //確定結(jié)點(diǎn)是否存在</p><p><b>　　int t;</b></p>

51、<p>　　for(int i=0;i<MAX;i++)</p><p>　　if(vexs[i]==v)</p><p><b>　　t=i;</b></p><p><b>　　return t;</b></p><p><b>　　}</b></p&

52、gt;<p>　　MGraph CreateMarph(MGraph &G){</p><p>　　int v1,v2,weight,i,j,k;</p><p>　　printf("●●請(qǐng)輸入無向圖的頂點(diǎn)數(shù)和邊數(shù)：");</p><p>　　scanf("%d%d",&G.vexnum,&

53、;G.arcnum);</p><p>　　for(i=0;i<G.vexnum;i++){ //初始化鄰接矩陣</p><p>　　for(j=0;j<G.vexnum;j++){</p><p>　　G.arcs[i][j]=0;</p><p><b>　　}}</b></p>

54、<p>　　for(i=0;i<G.vexnum;i++){</p><p>　　printf("第%d個(gè)頂點(diǎn)的序號(hào)：",i+1);</p><p>　　scanf("%d",&G.vexs[i]);</p><p><b>　　}</b></p><p&g

55、t;　　printf("\n---------------請(qǐng)你確定各條弧的信息--------------\n");</p><p>　　for(k=0;k<G.arcnum;k++)</p><p>　　{printf("●●請(qǐng)輸入第%d弧的兩個(gè)起始頂點(diǎn)和其權(quán)值為：",k+1);//輸入一條邊及依附的頂點(diǎn)及權(quán)值</p><

56、p><b>　　for(; ;){</b></p><p>　　scanf("%d%d%d",&v1,&v2,&weight);</p><p>　　if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum))<

57、;/p><p><b>　　break;</b></p><p><b>　　else</b></p><p>　　printf("輸入有誤，不存在該頂點(diǎn)，請(qǐng)重新輸入^_^\n");</p><p><b>　　}</b></p><p>

58、;　　i=LocateVex(G.vexs,v1); //找到兩個(gè)結(jié)點(diǎn)在鄰接矩陣中的位置</p><p>　　j=LocateVex(G.vexs,v2);</p><p>　　G.arcs[i][j]=weight; //邊的權(quán)值</p><p>　　G.arcs[j][i]=G.arcs[i][j];

59、 //置(v1,v2)成(v2,v1)</p><p><b>　　}</b></p><p>　　printf("-----------------------------------------------\n");</p><p><b>　　return G;</b></p

60、><p><b>　　}</b></p><p>　　struct closed{</p><p>　　int adjvex; //依附于最小權(quán)值邊在頂點(diǎn)集合U中的頂點(diǎn)</p><p>　　int lowcost; //存儲(chǔ)最小邊的權(quán)值</p><p><b>　　};<

61、/b></p><p>　　closed closedge[MAX];</p><p>　　void MiniTree_PRIM(MGraph G,int u){</p><p><b>　　int k=u;</b></p><p><b>　　int i,j;</b></p>

62、<p>　　for(i=0;i<G.vexnum;i++) //初始化closedge數(shù)組，v={u}</p><p>　　if(i!=k) //兩個(gè)頂點(diǎn)不重合</p><p>　　{closedge[i].adjvex=u+1; //首先將u視為第一條邊的第一個(gè)依附頂點(diǎn)</p><p>　　if(!G.arcs[k]

63、[i]) //兩點(diǎn)之間不連通</p><p>　　closedge[i].lowcost=-1;</p><p><b>　　else</b></p><p>　　closedge[i].lowcost=G.arcs[k][i]; //調(diào)整closedge數(shù)組的最小代價(jià)lowcost為邊上的權(quán)值</p><

64、;p><b>　　}</b></p><p>　　closedge[k].lowcost=0;</p><p>　　for(i=0;i<G.vexnum-1;i++) { //★取其余G.vexnum-1個(gè)頂點(diǎn)，循環(huán)從此處開始，i無任何意義</p><p>　　for(j=0;j<G.vexnum;j+

65、+)</p><p>　　if(closedge[j].lowcost>0){ //求出T的下一個(gè)結(jié)點(diǎn)，第K結(jié)點(diǎn)</p><p><b>　　k=j;</b></p><p><b>　　break;}</b></p><p>　　for(j=0;j<G.vexn

66、um;j++)</p><p>　　if(closedge[j].lowcost>0)</p><p>　　if(closedge[j].lowcost<closedge[k].lowcost) //比較權(quán)值大小,從中找出權(quán)值最小的邊</p><p><b>　　k=j;</b></p><p>　　pri

67、ntf(" %d -----------------> %d ( %d )\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);</p><p>　　closedge[k].lowcost=0; //將此第k個(gè)頂點(diǎn)并入U(xiǎn)集中</p><p>　　for(j=0;j<G.vex

68、num;j++) ////在頂點(diǎn)k并入U(xiǎn)之后， 更新closedge[i]，新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊</p><p>　　if(G.arcs[k][j]>0){ </p><p>　　if(closedge[j].lowcost==-1){ //如果先前時(shí)此兩個(gè)頂點(diǎn)之間是不連通的</p><p>　　cl

69、osedge[j].lowcost=G.arcs[k][j]; //新的權(quán)值域改成新加入頂點(diǎn)與該頂點(diǎn)的權(quán)值</p><p>　　closedge[j].adjvex=G.vexs[k];}</p><p>　　else //如果此前兩頂點(diǎn)本已連通</p><p>　　if(G.arcs[k][j]<cl

70、osedge[j].lowcost){ //調(diào)整closedge數(shù)組中各邊的最小權(quán)值</p><p>　　closedge[j].adjvex=G.vexs[k]; //依附于最小權(quán)值邊在U中的頂點(diǎn)</p><p>　　closedge[j].lowcost=G.arcs[k][j]; //邊的權(quán)值賦給closedge數(shù)組的最小權(quán)值域</p><p><

71、b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void menu(){</p><p>　　printf("\t

72、\t\t\t 【PRIM算法】\n");</p><p>　　printf("\t\t\t ★任意給定的網(wǎng)和起點(diǎn)★\n");</p><p>　　printf("\t\t 〓〓 求 解 出 所 有 的 最 小 生 成 樹 〓〓\n");</p><p><b>　　}</b>&l

73、t;/p><p>　　void LJ(MGraph G){</p><p>　　int i,j,t;</p><p>　　printf("是否輸出該圖的鄰接矩陣：\n");</p><p>　　printf(" ▼1-----------是\n");</p><p>　　

74、printf(" ▼0-----------否\n");</p><p><b>　　for(; ;){</b></p><p>　　scanf("%d",&t);</p><p><b>　　if(t==1){</b></p><p>　

75、　printf("★★建立的鄰接矩陣如下★★\n");</p><p>　　for(i=0;i<G.vexnum;i++){</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　printf("%d ",G.arcs[i][j]);</p><p>　　p

76、rintf("\n");}</p><p><b>　　break;}</b></p><p>　　else if(t==0)</p><p><b>　　break;</b></p><p><b>　　else</b></p><p&

77、gt;　　printf("輸入有誤，請(qǐng)重新輸入!^_^\n");</p><p><b>　　}</b></p><p>　　printf("-----------------------------------------------\n");</p><p><b>　　}</b>

78、;</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int w;</b></p><p><b>　　MGraph G;</b></p><p><b>　　menu();<

79、/b></p><p>　　CreateMarph(G);</p><p><b>　　LJ(G);</b></p><p>　　printf("我們可以從不同頂點(diǎn)開始來生成所有的最小生成樹，可如下\n");</p><p>　　for(w=0;w<G.vexnum;w++)</p&

80、gt;<p>　　{printf("■從頂點(diǎn)%d開始的最小生成樹：\n",w+1);</p><p>　　printf("頂點(diǎn)----------------->頂點(diǎn) (權(quán)值) \n");</p><p>　　MiniTree_PRIM(G,w);</p><p>　　printf("\n&quo