PAGE24-《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告建立通信網(wǎng)絡(luò)在n個城市建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。設(shè)計算法，求出如果以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)絡(luò)。要求如下：至少包含10個城市；城市數(shù)n由鍵盤錄入；城市坐標(biāo)由隨機函數(shù)產(chǎn)生小于100的整數(shù)；輸出生成樹中各條邊以及它們的權(quán)值；一、課程設(shè)計題目對任意給定的網(wǎng)和起點，用PRIM算法的基本思想求解出所有的最小生成樹。在n個城市建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。設(shè)計算法，求出如果以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)絡(luò)。二、問題分析和任務(wù)定義本課程設(shè)計重在使用prim算法實現(xiàn)任意給定的網(wǎng)和起點的圖的所有最小生成樹的求解，實現(xiàn)本課程設(shè)計的關(guān)鍵即是能夠掌握prim算法的思想，并能夠靈活使用。首先我們必須對prim算法有個清晰地認識，prim算法是普利姆（Prime）于1957年提出了一種構(gòu)造最小生成樹的算法，算法的主要思想如下：按照將頂點逐個連通的步驟，把頂點加入到已經(jīng)連通的頂點集合U中，最后使得U成為最小生成樹。PRIM思路：1）初始化頂點集合U為空集。2）任意選取一個頂點v加入U。3）選取一條權(quán)值最小的邊（u,v），其中u∈U，v∈（V-U），將該邊假如到生成樹，v加入到U中。4）重復(fù)步驟3），直到所有頂點均加入到U中構(gòu)成一顆最小生成樹。為了實現(xiàn)這一算法需要附設(shè)一個輔助數(shù)組closedge[v]用來存儲從U到V-U之間具有最小代價的邊。對于每個頂點v∈（V-U），在closedge，樹組中都存在一個分量closedge[v]，它有兩個域組成。其中一個是權(quán)值，即：closedge[v].lowcost=MIN{cost（u,v）|u∈U}，另外一個是頂點域vexs，存儲依附于該邊在U中的頂點。其次，針對本課程設(shè)計的題目要求，我們需要考慮到五個問題：如何選擇、設(shè)計一個合適的算法來建立圖，用以實現(xiàn)接下來的操作。如何正確的在本實驗中使用prim算法。對于本課程設(shè)計中的需要，求出對于給定任意給定的網(wǎng)和結(jié)點，得出所有的最小生成樹，關(guān)鍵在于需要求出所有的最小生成樹，需要靈活使用prim算法實現(xiàn)。對于一些細節(jié)也是需要考慮斟酌的，比如，當(dāng)所輸入的頂點不存在時，需要一個示語句警示，并能夠重新輸入。當(dāng)算法設(shè)計完成后，還需對于整個運行程序的運行界面，提示語句以及如何完美、清楚的輸出各個最小生成樹設(shè)計一番。最后，在課程設(shè)計過程中，自己需要做好充足的準(zhǔn)備工作，吃透課本中關(guān)于prim算法的解釋說明，同時把握好時間，掌握整個課程設(shè)計的進度，做好整體規(guī)劃，保證本次課程設(shè)計可以及時的、成功的設(shè)計出來。概要設(shè)計對于本次設(shè)計，在prim算法中使用的圖均為無向圖，對于各頂點之間的權(quán)值以及連通關(guān)系是采用鄰接矩陣來實現(xiàn)的。同時在prim算法中采用了輔助數(shù)組closedge[v]，主要用來存儲到頂點的最小邊權(quán)值。建立圖的數(shù)據(jù)結(jié)構(gòu)類型如下：typedefstruct{ intvexs[MAX];//頂點信息集合 intarcs[MAX][MAX];//各邊的權(quán)值 intvexnum;//頂點數(shù) intarcnum;//邊數(shù)}MGraph;//圖類型建立輔助數(shù)組結(jié)構(gòu)類型如下：structclosed{ intadjvex;//依附于最小權(quán)值邊在頂點集合U中的頂點 intlowcost;//存儲最小邊的權(quán)值};closedclosedge[MAX];3.1整個算法概要設(shè)計主要在于圖的初始化如何求出所有最小生成樹。下面我們可以通過相應(yīng)的流程圖來清楚的理解。剛開始時初始化各頂點的頂點域、權(quán)值域賦值的算法流程:開始開始把1賦給j把1賦給j 判斷j是否等于輸入的頂點數(shù)值判斷j是否等于輸入的頂點數(shù)值 j不等于I把I的值賦給j的頂點域里；把I的值賦給j的頂點域里；把鄰接矩陣中處于[j][I]位置的值賦給j的權(quán)值域中。 j等于I把j+1賦給j把j+1賦給j判斷j是否小于等于圖的頂點數(shù)判斷j是否小于等于圖的頂點數(shù) 小于等于 大于把0賦給頂點I的權(quán)值域把0賦給頂點I的權(quán)值域3.1.1求出最小代價的邊的算法流程把1賦給把1賦給j把1賦給i把1賦給i把鄰接矩陣中處于[1][i]位置的值賦給i的權(quán)值域中;把鄰接矩陣中處于[1][i]位置的值賦給i的權(quán)值域中;把1賦給i的頂點域中把i+1賦給i把i+1賦給i判斷i是否小于圖的頂點數(shù)判斷i是否小于圖的頂點數(shù) 小于 大于等于把0賦給1的頂點域中，把0賦給1的頂點域中，把1賦給j此時j的權(quán)值域是否小于minj的頂點域是否等于0j的頂點域是否等于0把1賦給j把100賦給min,把i的值賦給k.把1賦給i

有一個條件不滿足都是肯定的回答此時j的權(quán)值域是否小于minj的頂點域是否等于0j的頂點域是否等于0把1賦給j把100賦給min,把i的值賦給k.把1賦給i把頂點j里的權(quán)值域中的值賦給最小值min，把j賦給k 把頂點j里的權(quán)值域中的值賦給最小值min，把j賦給k把j+1賦給j把j+1賦給j判斷j是否小于等于圖的頂點數(shù)判斷j是否小于等于圖的頂點數(shù) 是 否用兩個頂點的集合輸出邊。用兩個頂點的集合輸出邊。 將頂點k加入到U中，表示k頂點已拿走了，把0賦給k的權(quán)值域中，這是標(biāo)志性的賦值。將頂點k加入到U中，表示k頂點已拿走了，把0賦給k的權(quán)值域中，這是標(biāo)志性的賦值。對于上述流程圖可簡單解釋如下，首先通過對其它頂點依次判斷，找出相連的頂點，然后得到頂點序號，再通過for循環(huán)，進行循環(huán)判斷，找出邊權(quán)值最小的，并賦值進入closedge[]中。3.2重新調(diào)整各頂點中的頂點域和權(quán)值域的流程:把1賦給m把1賦給m在鄰接矩陣中[k][m]存的值是否小于頂點m權(quán)值域中的值，m不等于k在鄰接矩陣中[k][m]存的值是否小于頂點m權(quán)值域中的值，m不等于k 有一個不滿足 答案是肯定的把鄰接矩陣[k][m]存的值給頂點m的權(quán)值域，把頂點k給m的頂點域把鄰接矩陣[k][m]存的值給頂點m的權(quán)值域，把頂點k給m的頂點域 把m+1賦給m把m+1賦給mm是否小于等于圖mg的頂點數(shù)m是否小于等于圖mg的頂點數(shù) 是的否循環(huán)到求最小代價邊的算法中.循環(huán)到求最小代價邊的算法中.3.3普利姆算法的總流程將各頂點的頂點域、權(quán)值域賦值。將各頂點的頂點域、權(quán)值域賦值。求出最小代價的邊。重新調(diào)整各頂點中的頂點域和權(quán)值域。輸出邊的頂點信息結(jié)束開始j小于圖的頂點數(shù) 是 否 3.4主函數(shù)的流程開始開始定義g為鄰接矩陣數(shù)據(jù)類型定義g為鄰接矩陣數(shù)據(jù)類型輸入頂點數(shù)，邊數(shù)。輸入頂點數(shù)，邊數(shù)。把頂點數(shù)和邊數(shù)賦給鄰接矩陣g把頂點數(shù)和邊數(shù)賦給鄰接矩陣g把0賦給i把0賦給i輸入第i個頂點的信息。循環(huán)輸入所有頂點的信息輸入第i個頂點的信息。循環(huán)輸入所有頂點的信息循環(huán)輸入邊的起點和終點循環(huán)輸入邊的起點和終點如果超出編號范圍，則重新輸入。如果超出編號范圍，則重新輸入。循環(huán)輸出各邊的權(quán)值。循環(huán)輸出各邊的權(quán)值。調(diào)用鄰接矩陣的初始化函數(shù)、創(chuàng)建函數(shù)、PRIM函數(shù)。調(diào)用鄰接矩陣的初始化函數(shù)、創(chuàng)建函數(shù)、PRIM函數(shù)。結(jié)束結(jié)束詳細設(shè)計4.1圖的建立MGraphCreateMarph(MGraph&G){ intv1,v2,weight,i,j,k; printf("●●請輸入無向圖的頂點數(shù)和邊數(shù)："); scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++){//初始化鄰接矩陣 for(j=0;j<G.vexnum;j++){ G.arcs[i][j]=0; }} for(i=0;i<G.vexnum;i++){ printf("第%d個頂點的序號：",i+1); scanf("%d",&G.vexs[i]); } printf("\n請你確定各條弧的信息\n"); for(k=0;k<G.arcnum;k++) {printf("●●請輸入第%d弧的兩個起始頂點和其權(quán)值為：",k+1);//輸入一條邊及依附的頂點及權(quán)值 for(;;){scanf("%d%d%d",&v1,&v2,&weight); if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum)) break; else printf("輸入有誤，不存在該頂點，請重新輸入^_^\n"); } i=LocateVex(G.vexs,v1);//找到兩個結(jié)點在鄰接矩陣中的位置 j=LocateVex(G.vexs,v2); G.arcs[i][j]=weight;//邊的權(quán)值 G.arcs[j][i]=G.arcs[i][j];//置(v1,v2)成(v2,v1) } printf("\n"); returnG; }本子函數(shù)是用來建立圖，其中用到了鄰接矩陣用以存儲各邊的權(quán)值以及判斷是否連通，其中所調(diào)用的LocateVex()是用來指出該頂點在鄰接矩陣中所在的位置，其子函數(shù)定義如下：intLocateVex(intvexs[],intv){//確定結(jié)點是否存在intt; for(inti=0;i<MAX;i++)if(vexs[i]==v)t=i; returnt;}4.2使用Prim算法實現(xiàn)找出圖中的最小生成樹voidMiniTree_PRIM(MGraphG,intu){ intk=u; inti,j; for(i=0;i<G.vexnum;i++)//初始化closedge數(shù)組，v={u} if(i!=k)//兩個頂點不重合 {closedge[i].adjvex=u+1;//首先將u視為第一條邊的第一個依附頂點 if(!G.arcs[k][i])//兩點之間不連通 closedge[i].lowcost=-1; else closedge[i].lowcost=G.arcs[k][i];//調(diào)整closedge數(shù)組的最小代價lowcost為邊上的權(quán)值 } closedge[k].lowcost=0; for(i=0;i<G.vexnum-1;i++){//★取其余G.vexnum-1個頂點，循環(huán)從此處開始，i無任何意義 for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0){//求出T的下一個結(jié)點，第K結(jié)點 k=j; break;} for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0) if(closedge[j].lowcost<closedge[k].lowcost)//比較權(quán)值大小,從中找出權(quán)值最小的邊 k=j; printf("%d>%d(%d)\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost); closedge[k].lowcost=0;//將此第k個頂點并入U集中 for(j=0;j<G.vexnum;j++)////在頂點k并入U之后，更新closedge[i]，新頂點并入U后重新選擇最小邊 if(G.arcs[k][j]>0){ if(closedge[j].lowcost==-1){//如果先前時此兩個頂點之間是不連通的 closedge[j].lowcost=G.arcs[k][j];//新的權(quán)值域改成新加入頂點與該頂點的權(quán)值 closedge[j].adjvex=G.vexs[k];} else//如果此前兩頂點本已連通 if(G.arcs[k][j]<closedge[j].lowcost){//調(diào)整closedge數(shù)組中各邊的最小權(quán)值 closedge[j].adjvex=G.vexs[k];//依附于最小權(quán)值邊在U中的頂點 closedge[j].lowcost=G.arcs[k][j];//邊的權(quán)值賦給closedge數(shù)組的最小權(quán)值域 } } }}其中要說明的是其中使用了一個輔助數(shù)組，其定義如下：structclosed{ intadjvex;//依附于最小權(quán)值邊在頂點集合U中的頂點 intlowcost;//存儲最小邊的權(quán)值};此數(shù)組對PRIM中產(chǎn)生的頂點和邊的權(quán)值進行臨時存儲的數(shù)組，因此結(jié)構(gòu)體中設(shè)計兩個變量，頂點名adjvex，邊的權(quán)值lowcost。定義次數(shù)組名為closedclosedge[MAX]在用PRIM算法計算圖的最小生成樹過程中，這里是整個算法的核心之所在。先要指定點u最為最小生成樹的起點，并以次來構(gòu)成最小生成樹，子函數(shù)中用k來作為u的載體，同時它也是u在圖中的位置，后對輔助數(shù)組closedge進行初始化，首先將u視為第一條邊的第一個依附頂點，從零開始，所以u+1。如果兩點間不連通則給邊的權(quán)值lowcost賦值-1；否則將選擇的邊的權(quán)值adj賦給loecost，即將起存儲在輔助數(shù)組中。而后開始尋找下一個結(jié)點，進行邊的權(quán)值的比較，選擇出最小權(quán)值的邊。將該邊的頂點和權(quán)值存儲入輔助數(shù)組中，然后重新選擇最小邊，如此重復(fù)直至結(jié)束。將在次過程中選擇的邊的頂點和權(quán)值全部存儲進輔助數(shù)組中。而后開始調(diào)整輔助數(shù)組中各個邊的最小權(quán)值，在輔助數(shù)組中生成最小生成樹。最后將存儲在輔助數(shù)組中的最小生成樹輸出。其中，使用多個FOR的套嵌來實現(xiàn)最小權(quán)值邊的選擇。數(shù)組在這過程中始終作為臨時存儲空間，將篩選出的邊的信息存儲著，最后將其輸出來。4.3可建立由五點構(gòu)建的圖如下鄰接矩陣鄰接矩陣414132656665552134普利姆算法中closedge數(shù)組的變化Vclosedge23456UV-UVexLowcostV1 V1V16 15 1 2,3,4,5,6VexLowcostV3 V1V3V305 5 6 41,32,4,5,6VexLowcostV3V6V300526 1,3,62,4,5VexLowcostV3V3000561,3,6,42,5VexLowcostV2000031,2,3,4,65VexLowcost00 0001,2,3,4,5,6 最后以頂點1開始所生成的最小生成樹如下：441326552134五、調(diào)試通過調(diào)試分析，發(fā)現(xiàn)此程序中的closedge數(shù)組變化是一個難點，其中的數(shù)值變化時整個課程設(shè)計的關(guān)鍵，或多或少有點繁瑣，不容易掌握清楚。對一些特殊情況沒有考慮到，從而造成本設(shè)計出來的程序不全面，如在輸入圖中頂點信息時，沒有考慮到輸入的頂點不存在的情況。如果數(shù)據(jù)之間的類型不同，會引發(fā)數(shù)據(jù)間交換紊亂。指針空間未分配而導(dǎo)致系統(tǒng)隨機給出個錯誤數(shù)據(jù)。地址相沖突導(dǎo)致的程序錯誤。這些都沒有語法錯誤但是在調(diào)試中將引起亂碼，是個重要的問題，而且會頻繁出現(xiàn)。因此要多調(diào)試，思考以解決這些問題。在尋找下一結(jié)點時，尋找到最小權(quán)值邊，將其兩端的頂點信息及變的權(quán)值存儲到輔助樹組中。在設(shè)計解決這些問題的時候用多個for進行套嵌實現(xiàn)查找、判斷。因為本程序使用的是prim算法，for循環(huán)的使用套嵌較復(fù)雜，因此在設(shè)計時要理清思路。時間、空間性能分析。根據(jù)程序中的循環(huán)語句可以判斷出普利姆算法的時間復(fù)雜度為O(n2)。算法和圖中邊的數(shù)目無關(guān)，因此普利姆算法適合于求稠密網(wǎng)的最小生成樹。因為在算法中運用了鄰接矩陣的存儲結(jié)構(gòu)，在無向圖中，鄰接矩陣是對稱的。所以僅需要存儲上三角(下三角)的元素，因此需要n(n+1)個存儲空間。六、測試441326566655521346.1對于上圖測試結(jié)果如下所示：七、心得體會本程序是在MicrosoftVisualC++環(huán)境下運行，經(jīng)過本人調(diào)試運行成功。運行過程時帶有提示性語句。由于是求解圖的最小生成樹，因此先進行圖的頂點數(shù)和邊數(shù)的輸入。然后對各個頂點進行頂點信息的輸入。接著對各個邊的起點、終點、權(quán)值進行輸入。在其過程中若輸入不存在的頂點時會有語句提示，并且重新輸入。然后是選擇是否輸出所建圖的的鄰接矩陣，若輸入有錯誤時會有提示語句，并重新選擇。最后輸出的是按各頂點為起點輸出所有的最小生成樹。八、附錄（源程序）#include"stdio.h"#include"stdlib.h"#include"malloc.h"#defineMAX20typedefstruct{ intvexs[MAX];//頂點信息集合 intarcs[MAX][MAX];//各邊的權(quán)值 intvexnum;//頂點數(shù) intarcnum;//邊數(shù)}MGraph;intLocateVex(intvexs[],intv){//確定結(jié)點是否存在intt; for(inti=0;i<MAX;i++)if(vexs[i]==v)t=i; returnt;}MGraphCreateMarph(MGraph&G){ intv1,v2,weight,i,j,k; printf("請輸入無向圖的頂點數(shù)和邊數(shù)："); scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++){//初始化鄰接矩陣 for(j=0;j<G.vexnum;j++){ G.arcs[i][j]=0; }} for(i=0;i<G.vexnum;i++){ printf("第%d個頂點的序號：",i+1); scanf("%d",&G.vexs[i]); } printf("\n請你確定各條弧的信息\n"); for(k=0;k<G.arcnum;k++) {printf("請輸入第%d弧的兩個起始頂點和其權(quán)值為：",k+1);//輸入一條邊及依附的頂點及權(quán)值 for(;;){scanf("%d%d%d",&v1,&v2,&weight); if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum)) break; else printf("輸入有誤，不存在該頂點，請重新輸入^_^\n"); } i=LocateVex(G.vexs,v1);//找到兩個結(jié)點在鄰接矩陣中的位置 j=LocateVex(G.vexs,v2); G.arcs[i][j]=weight;//邊的權(quán)值 G.arcs[j][i]=G.arcs[i][j];//置(v1,v2)成(v2,v1) } printf("\n"); returnG; }structclosed{ intadjvex;//依附于最小權(quán)值邊在頂點集合U中的頂點 intlowcost;//存儲最小邊的權(quán)值};closedclosedge[MAX];voidMiniTree_PRIM(MGraphG,intu){ intk=u; inti,j; for(i=0;i<G.vexnum;i++)//初始化closedge數(shù)組，v={u} if(i!=k)//兩個頂點不重合 {closedge[i].adjvex=u+1;//首先將u視為第一條邊的第一個依附頂點 if(!G.arcs[k][i])//兩點之間不連通 closedge[i].lowcost=-1; else closedge[i].lowcost=G.arcs[k][i];//調(diào)整closedge數(shù)組的最小代價lowcost為邊上的權(quán)值 } closedge[k].lowcost=0; for(i=0;i<G.vexnum-1;i++){//★取其余G.vexnum-1個頂點，循環(huán)從此處開始，i無任何意義 for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0){//求出T的下一個結(jié)點，第K結(jié)點 k=j; break;} for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0) if(closedge[j].lowcost<closedge[k].lowcost)//比較權(quán)值大小,從中找出權(quán)值最小的邊 k=j; printf("%d>%d(%d)\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost); closedge[k].lowcost=0;//將此第k個頂點并入U集中 for(j=0;j<G.vexnum;j++)////在頂點k并入U之后，更新closedge[i]，新頂點并入U后重新選擇最小邊 if(G.arcs[k][j]>0){ if(closedge[j].lowcost==-1){