離散數(shù)學(xué)-最小生成樹實(shí)驗(yàn)報(bào)告

/實(shí)驗(yàn)?zāi)康模赫莆請(qǐng)D的存儲(chǔ)表示和以及圖的最小生成樹算法。二、實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)圖的存儲(chǔ).并且讀入圖的內(nèi)容。利用克魯斯卡爾算法求網(wǎng)絡(luò)的最小生成樹。實(shí)現(xiàn)構(gòu)造生成樹過(guò)程中的連通分量抽象數(shù)據(jù)類型。以文本形式輸出對(duì)應(yīng)圖的最小生成樹各條邊及權(quán)值。三、實(shí)驗(yàn)要求：在上機(jī)前寫出全部源程序；能在機(jī)器上正確運(yùn)行程序；用戶界面友好。需求分析：1、利用克魯斯卡爾算法求網(wǎng)的最小生成樹；2、以用戶指定的結(jié)點(diǎn)為起點(diǎn),分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列；3、輸入為存在邊的頂點(diǎn)對(duì).以及它們之間的權(quán)值；輸出為所得到的鄰接矩陣以及按權(quán)排序后的邊和最后得到的最小生成樹；克魯斯卡爾算法：假設(shè)WN=<V,{E}>是一個(gè)含有n個(gè)頂點(diǎn)的連通網(wǎng).按照構(gòu)造最小生成樹的過(guò)程為：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn).而邊集為空的子圖.之后.從網(wǎng)的邊集E中選取一條權(quán)值最小的邊.若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹.則將其加入子圖.反之.若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上.則不可取.而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推.直至只有一棵樹.也即子圖中含有n-1條邊為止。測(cè)試數(shù)據(jù)：自行指定圖進(jìn)行運(yùn)算四、詳細(xì)設(shè)計(jì)源程序#include<stdio.h>#include<stdlib.h>#defineM20#defineMAX20typedefstruct{intbegin;intend;intweight;}edge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,arcnum;}MGraph;voidCreatGraph<MGraph*>;voidsort<edge*,MGraph*>;voidMiniSpanTree<MGraph*>;intFind<int*,int>;voidSwapn<edge*,int,int>;voidCreatGraph<MGraph*G>{inti,j,n,m;printf<"請(qǐng)輸入邊數(shù)和頂點(diǎn)數(shù):">;scanf<"%d%d",&G->arcnum,&G->vexnum>;for<i=1;i<=G->vexnum;i++>{for<j=1;j<=G->vexnum;j++>{G->arc[i][j].adj=G->arc[j][i].adj=0;}}for<i=1;i<=G->arcnum;i++>{printf<"\n請(qǐng)輸入有邊的2個(gè)頂點(diǎn)">;scanf<"%d%d",&n,&m>;while<n<0||n>G->vexnum||m<0||n>G->vexnum>{printf<"輸入的數(shù)字不符合要求請(qǐng)重新輸入:">;scanf<"%d%d",&n,&m>;}G->arc[n][m].adj=G->arc[m][n].adj=1;getchar<>;printf<"\n請(qǐng)輸入%d與%d之間的權(quán)值:",n,m>;scanf<"%d",&G->arc[n][m].weight>;}printf<"鄰接矩陣為:\n">;for<i=1;i<=G->vexnum;i++>{for<j=1;j<=G->vexnum;j++>{printf<"%d",G->arc[i][j].adj>;}printf<"\n">;}}voidsort<edgeedges[],MGraph*G>{inti,j;for<i=1;i<G->arcnum;i++>{for<j=i+1;j<=G->arcnum;j++>{if<edges[i].weight>edges[j].weight>{Swapn<edges,i,j>;}}}printf<"權(quán)排序之后的為:\n">;for<i=1;i<G->arcnum;i++>{printf<"<<%d,%d>>%d\n",edges[i].begin,edges[i].end,edges[i].weight>;}}voidSwapn<edge*edges,inti,intj>{inttemp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].weight;edges[i].weight=edges[j].weight;edges[j].weight=temp;}voidMiniSpanTree<MGraph*G>{inti,j,n,m;intk=1;intparent[M];edgeedges[M];for<i=1;i<G->vexnum;i++>{for<j=i+1;j<=G->vexnum;j++>{if<G->arc[i][j].adj==1>{edges[k].begin=i;edges[k].end=j;edges[k].weight=G->arc[i][j].weight;k++;}}}sort<edges,G>;for<i=1;i<=G->arcnum;i++>{parent[i]=0;}printf<"最小生成樹為:\n">;for<i=1;i<=G->arcnum;i++>{n=Find<parent,edges[i].begin>;m=Find<parent,edges[i].end>;if<n!=m>{parent[n]=m;printf<"<<%d,%d>>%d\n",edges[i].begin,edges[i].end,edges[i].weight>;}}}intFind<int*parent,intf>{while<parent[f]>0>{f=parent[f];}returnf;}intmain<void>{MGraph*G;G=<MGraph*>malloc<sizeof<MGraph>>;if<G==NULL>{printf<"memoryallcationfailed,goodbye">;exit<1>;}CreatGraph<G>;MiniSpanTree<G>;system<"pause">;return0;}運(yùn)行結(jié)果:五、實(shí)驗(yàn)總結(jié)〔結(jié)果分析和體會(huì)在編程時(shí).因?yàn)榭紤]的情況比較多.所以容易造成錯(cuò)誤和遺漏.為了避免這些問(wèn)題的出現(xiàn).可以先用筆把所有的程序在紙上.然后再根據(jù)列表編寫程序.這樣不僅簡(jiǎn)單易懂.還避免了一些不必要的錯(cuò)誤。編寫完程序后進(jìn)行調(diào)試.發(fā)現(xiàn)有很多錯(cuò)誤.其中也不乏一些基本的小錯(cuò)誤.所以程序?qū)懲旰筮M(jìn)行靜態(tài)檢查是必不可少的.其次是邏輯上的錯(cuò)誤.對(duì)于這些錯(cuò)誤.只能再認(rèn)真檢查整個(gè)程序.這就要求我們?cè)诰幊虝r(shí)考慮要周到.或者可以請(qǐng)其他同學(xué)幫忙檢查。通過(guò)這次對(duì)算術(shù)表達(dá)式求值的設(shè)計(jì).讓我自己對(duì)克魯斯卡爾算法的運(yùn)用更深刻.能