最小生成樹prim算法

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告〔最小生成樹問題〕1課程設(shè)計(jì)的目的和意義2需求分析3系統(tǒng)〔工程〕設(shè)計(jì)4系統(tǒng)實(shí)現(xiàn)5系統(tǒng)調(diào)試附錄源程序1課程設(shè)計(jì)的目的和意義據(jù)《數(shù)據(jù)結(jié)構(gòu)》課堂講授及書本內(nèi)容，學(xué)生做相應(yīng)的自主練習(xí)，消化課堂所講解的內(nèi)容；通過調(diào)試典型例題或習(xí)題積累調(diào)試C及C++程序的經(jīng)驗(yàn)；通過完成課程設(shè)計(jì)中的編程題，逐漸培養(yǎng)學(xué)生的編程能力、用計(jì)算機(jī)解決實(shí)際問題的能力?！皵?shù)據(jù)結(jié)構(gòu)”作為計(jì)算機(jī)專業(yè)根底課，該課程的目標(biāo)就是使學(xué)生學(xué)會如何從問題出發(fā)，分析數(shù)據(jù)，構(gòu)造求解問題的數(shù)據(jù)結(jié)構(gòu)和算法，培養(yǎng)學(xué)生有一定進(jìn)行較復(fù)雜程序設(shè)計(jì)的能力。本次課程設(shè)計(jì)的內(nèi)容是用最小生成樹的構(gòu)造來表示城市間的最小代價即最小距離，最小生成樹可以用連接矩陣和連接表表示，而它們的區(qū)別就是連接矩陣一般用來表示密集型的網(wǎng)絡(luò)，連接表一般用來表示稀疏型的網(wǎng)絡(luò)，連接矩陣是用數(shù)組來存儲，連接了是用鏈表來存儲的，比擬復(fù)雜密集型的網(wǎng)絡(luò)就網(wǎng)連接矩陣較適用了，設(shè)計(jì)中運(yùn)用了Prim算法，“構(gòu)造可以使n個城市連接的最小生成樹”問題就是用連接矩陣和Prim算法處理的一個實(shí)際應(yīng)用。通過這個題目的設(shè)計(jì)實(shí)例，了解了最小生成樹的實(shí)際運(yùn)用意義，也了解連接矩陣和連接表的相同與不同之處，進(jìn)一步加深了對最小生成樹結(jié)構(gòu)和Prim算法的理解。通過這次課程設(shè)計(jì)，一方面使學(xué)生加深對課內(nèi)所學(xué)的有關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)和時空分析等課程根本內(nèi)容的理解，另一方面，使學(xué)生在程序設(shè)計(jì)方法〔如抽象數(shù)據(jù)類型、結(jié)構(gòu)化分析、模塊化設(shè)計(jì)和結(jié)構(gòu)化設(shè)計(jì)〕、C和C++語言編程環(huán)境以及程序的調(diào)試和測試方面受到比擬系統(tǒng)的嚴(yán)格的訓(xùn)練。2需求分析題目：最小生成樹的Prime算法實(shí)現(xiàn)〔難度**〕要求：先任意創(chuàng)立一個圖；用Prime算法，求出該圖的最小生成樹。3系統(tǒng)〔工程〕設(shè)計(jì)(包括總體設(shè)計(jì)和詳細(xì)設(shè)計(jì))一.設(shè)計(jì)思想及方案：n個頂點(diǎn)的連通圖應(yīng)該至少有n-1條邊，而生成樹正好有n-1條邊，所以生成樹是對應(yīng)的連通圖的極小連通子圖。帶權(quán)的無向圖，經(jīng)過遍歷得到的生成樹也是帶權(quán)的，最小生成樹即權(quán)值最小的生成樹。所以要求圖的最小生成樹，即只要求權(quán)值最小的極小連通子圖。這實(shí)際上是求圖的一個生成樹。同時還要考慮造價最低這個條件。一棵樹的權(quán)定義為它所含各邊的權(quán)之和。一個連通網(wǎng)絡(luò)的最小生成樹是該圖所有生成樹中權(quán)最小的生成樹普里姆算法〔Prim〕算法：設(shè)N=〔V,{E}〕是連通圖，TE是N上最小生成樹中邊的集合，U為V中具有最小生成樹的頂點(diǎn)集合，初始時，TN為空，U={uo}(uo∈V),重復(fù)下敘操作：在所有u∈U、v∈V-U的邊〔u,v〕∈E中找一條代價最小的邊〔u0，v0〕并入集合TE，同時v0并入集合TE,同時,直到U=V為止，此時TE必有n-1條邊，且T=(V,{TE})為N的最小生成樹。二．模塊的設(shè)計(jì)及介紹(1).主程序模塊voidmain(){{接受命令；處理命令；Cout<<endl<<””命令”=”是否繼續(xù)？y/n””;}}(2).創(chuàng)立鏈接矩陣模塊intcreatMGraph_L(參數(shù)){for{接受命令；處理命令；}cout<<"命令"<<endl;}4系統(tǒng)實(shí)現(xiàn)各模塊關(guān)鍵代碼及算法的解釋：〔1〕.主函數(shù)模塊代碼{algraphgra;MGraph_LG;inti,d,g[20][20];chara='a';d=creatMGraph_L(G);vnodev;cout<<endl<<"注意：假設(shè)該圖為非強(qiáng)連通圖(含有多個連通分量)時"<<endl<<"最小生成樹不存在,那么顯示為非法值"<<endl<<endl;cout<<"…菜單……"<<endl<<endl;cout<<"0、顯示該圖的鄰接矩陣……"<<endl;cout<<"1、最小生成樹PRIM算法及代價…"<<endl;ints;chary='y';while(y='y'){cout<<"請選擇菜單："<<endl;cin>>s;switch(s){case0:cout<<"鄰接矩陣顯示如下："<<endl;ljjzprint(G);break;case1:for(i=0;i!=G.vexnum;++i)for(intj=0;j!=G.vexnum;++j)g[i+1][j+1]=G.arcs[i][j].adj;cout<<"prim:"<<endl;prim(g,d);break;}cout<<endl<<"是否繼續(xù)？y/n:";cin>>y;if(y=='n')break;}}程序解釋：該主函數(shù)用一個循環(huán)語句，來執(zhí)行其它的函數(shù)的功能。從鍵盤輸入頂點(diǎn)數(shù)和邊數(shù)上限，再調(diào)用定義連接矩陣的函數(shù)，后輸出創(chuàng)立連接矩陣的信息，再調(diào)用creatMGraph〔〕函數(shù)，接著進(jìn)入菜單，然后再選擇輸入一個數(shù)確定是要輸出連接矩陣還是最小生成樹及代價，最后選擇輸入確定字母y或N確定是否繼續(xù)。(2).鄰接矩陣定義模塊代碼typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;intlocalvex(MGraph_LG,charv){inti=0;while(G.vexs[i]!=v){++i;}returni;}程序解釋：用typedefstruct定義連接矩陣，通過二維數(shù)組來存儲連接矩陣，并設(shè)定參數(shù)的最大值為20?！?〕.創(chuàng)立鏈接矩陣模塊代碼intcreatMGraph_L(MGraph_L&G){charv1,v2;inti,j,w;cout<<"…………創(chuàng)立無向圖〔城市分布圖〕…………"<<endl<<"請輸入圖G頂點(diǎn)〔城市〕和弧〔邊〕的個數(shù):(46)不包括“()”"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"輸入頂點(diǎn)〔城市〕"<<i<<endl;cin>>G.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(intk=0;k!=G.arcnum;++k){cout<<"輸入一條邊依附的頂點(diǎn)〔城市〕和權(quán)〔距離〕:(ab3)不包括“()”"<<endl;cin>>v1>>v2>>w;i=localvex(G,v1);j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout<<"圖G鄰接矩陣創(chuàng)立成功！"<<endl;returnG.vexnum;}程序解釋：該語句是從鍵盤輸入頂點(diǎn)數(shù)和邊數(shù)，輸入頂點(diǎn)和權(quán)值，通過循環(huán)語句的調(diào)用，最后調(diào)用creatMGraph_L〔〕創(chuàng)立連接矩陣(4).最小生成樹Prim算法及代價模塊代碼intprim(intg[][max],intn){intlowcost[max],prevex[max];inti,j,k,min;intsum=o;for(i=2;i<=n;i++){lowcost[i]=g[1][i];//初始化prevex[i]=1;}lowcost[1]=0;for(i=2;i<=n;i++)//形成n-1條邊的生成樹{min=inf;k=0;for(j=2;j<=n;j++)if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);sum+=min;lowcost[k]=0;for(j=2;j<=n;j++)if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf("\n");}cout<<"最少生成樹的代價:";cout<<sum;return0;}程序解釋：該語句運(yùn)用一系列的循環(huán)語句來實(shí)現(xiàn)的，利用前面的創(chuàng)立好的鏈接矩陣，通過各邊權(quán)值的比擬，最后調(diào)用prim()函數(shù)，實(shí)現(xiàn)最小生成樹的生成，同時運(yùn)用sum把最小生成樹各邊權(quán)值相加得到最小生成樹的代價。5系統(tǒng)調(diào)試1、運(yùn)行程序后，初界面：2、輸入頂點(diǎn)和弧的個數(shù)后的界面：.3、輸入頂點(diǎn)后的界面：4、輸入一條邊依附的頂點(diǎn)和權(quán)值后的界面：5、輸入確定數(shù)字0及確定字母y后的界面：6、輸入確定數(shù)字1及確定字母n后的界面：小結(jié)回憶起此次課程設(shè)計(jì)，至今我仍感慨頗多，從理論到實(shí)踐，在整整一周的日子里，我學(xué)到很多很多的東西，不僅穩(wěn)固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的內(nèi)容。培養(yǎng)了獨(dú)立思考，深入研究，分析問題、解決問題的能力，提高綜合運(yùn)用本課程所學(xué)知識的能力，還對課程設(shè)計(jì)的基的設(shè)計(jì)方法、步驟、思路、有了深刻的了解與認(rèn)識，并對存儲結(jié)構(gòu)和函數(shù)的調(diào)用，比方連接矩陣、鏈接表、樹、圖等存儲結(jié)構(gòu)，for引導(dǎo)的循環(huán)語句，特別是Prim算法理解的更深。我本次課程設(shè)計(jì)的題目是構(gòu)造可以使n個城市連接的最小生成樹，開始看到題目覺得自己題目對自己比擬有利，因?yàn)樽约簩ψ钚∩蓸溥@節(jié)的內(nèi)容比擬熟悉，但是剛一開始編程覺得自己無從下手，這就看出自己的問題了，在書本上學(xué)的只是一些很淺薄的東西，在實(shí)際運(yùn)用中顯得很無力，但是通過自己慢慢查閱相關(guān)書籍和相關(guān)網(wǎng)站后，編程的進(jìn)度慢慢加快了，一些相關(guān)的難點(diǎn)逐步得到解決，最終還是完成了此次課程設(shè)計(jì)中最主要的幾個步驟。通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實(shí)踐相結(jié)合起來，從理論中得出結(jié)論，才是真正的知識，才能提高自己的實(shí)際動手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過程遇到了各種各樣的問題，同時在設(shè)計(jì)的過程中發(fā)現(xiàn)了自己的缺乏之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固，通過這次課程設(shè)計(jì)，把以前所學(xué)過的知識重新溫故，穩(wěn)固了所學(xué)的知識。源程序#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000//最大的頂點(diǎn)數(shù)#defineinf9999//將無法到達(dá)的權(quán)值無限大設(shè)為9999#definemax20//…………鄰接矩陣定義……typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^intlocalvex(MGraph_LG,charv)//返回V的位置{inti=0;while(G.vexs[i]!=v){++i;}returni;}intcreatMGraph_L(MGraph_L&G)//創(chuàng)立圖用鄰接矩陣表示{charv1,v2;inti,j,w;printf("請輸入頂點(diǎn)元素：\n");cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"輸入頂點(diǎn)"<<i<<endl;cin>>G.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(intk=0;k!=G.arcnum;++k){printf("請輸入邊兩端頂點(diǎn)序號和相應(yīng)的權(quán)值：\n");cin>>v1>>v2>>w;//輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,v1);//確定頂點(diǎn)V1和V2在圖中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout<<"圖G鄰接矩陣創(chuàng)立成功！"<<endl;returnG.vexnum;}voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<G.arcs[i][j].adj<<"";cout<<endl;}}intvisited[max];//訪問標(biāo)記intwe;typedefstructarcnode//邊結(jié)點(diǎn){intadjvex;//該邊指向的頂點(diǎn)的位置structarcnode*nextarc;//邊尾相同的下一條弧char*info;//該邊信息}arcnode;typedefstructvnode//鄰接鏈表頂點(diǎn)頭接點(diǎn){chardata;//結(jié)點(diǎn)信息arcnode*firstarc;//指向第一條依附該結(jié)點(diǎn)的邊的指針}vnode,adjlist;typedefstruct//圖的定義{adjlistvertices[max];intvexnum,arcnum;intkind;}algraph;intprim(intg[][max],intn)//最小生成樹PRIM算法{intlowcost[max],prevex[max];//LOWCOST[]存儲當(dāng)前集合U分別到剩余結(jié)點(diǎn)的最短路徑//prevex[]存儲最短路徑在U中的結(jié)點(diǎn)inti,j,k,min;intsum=0;for(i=2;i<=n;i++)//n個頂點(diǎn)，n-1條邊{lowcost[i]=g[1][i];//初始化prevex[i]=1;//頂點(diǎn)未參加到最小生成樹中}lowcost[1]=0;//標(biāo)志頂點(diǎn)1參加U集合for(i=2;i<=n;i++)//形成n-1條邊的生成樹{min=inf;k=0;for(j=2;j<=n;j++)//尋找滿足邊的一個頂點(diǎn)在U,另一個頂點(diǎn)在V的最小邊if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);sum+=min;lowcost[k]=0;//頂點(diǎn)k參加Ufor(j=2;j<=n;j++)//修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值if(g[k][j]<lowcost[j]){lowcost[j