數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 最小生成樹

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告最小生成樹問(wèn)題一、問(wèn)題描述：若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問(wèn)題基本要求（1）從文件中讀入圖的信息。（2）利用克魯斯卡爾算法求網(wǎng)的最小生成樹。（3）以文本形式生成樹中各條邊以及他們的權(quán)值。二．需求分析：1、需定義結(jié)構(gòu)體數(shù)組，根據(jù)權(quán)值逐一選擇邊。三．概要設(shè)計(jì)抽象數(shù)據(jù)類型：需定義結(jié)構(gòu)體數(shù)組，存儲(chǔ)每條邊的起點(diǎn)，終點(diǎn)，權(quán)值。算法的基本思想：圖的信息的讀?。憾x結(jié)構(gòu)體數(shù)組，存儲(chǔ)每條邊的起點(diǎn)，終點(diǎn)，權(quán)值。對(duì)每條邊在數(shù)組中的位置處理：選邊需從最小的開始，故按邊的權(quán)值從小到大進(jìn)行排序。邊的選?。簭淖钚〉倪叺拈_始，若邊的兩端點(diǎn)不屬于同一集合，則選取該邊。并將該邊的兩個(gè)頂點(diǎn)所在的兩個(gè)集合合并成為一個(gè)。因?yàn)橛衝個(gè)頂點(diǎn)，故只需選取n-1條邊。程序的流程：輸入模塊：讀入圖的信息（頂點(diǎn)和邊，用結(jié)構(gòu)體數(shù)組進(jìn)行存儲(chǔ)）。處理模塊：Kruskal算法。輸出模塊：將結(jié)果輸出。四．詳細(xì)設(shè)計(jì)：算法的具體步驟：structG{intfromvex;intendvex;intweight;}GE[100],cur[100];voidswap(G*GE,inti,intj){//交換函數(shù)inttemp=GE[i].fromvex;GE[i].fromvex=GE[j].fromvex;GE[j].fromvex=temp;temp=GE[i].endvex;GE[i].endvex=GE[j].endvex;GE[j].endvex=temp;temp=GE[i].weight;GE[i].weight=GE[j].weight;GE[j].weight=temp;}voidKruskal(intn){inti,j,k=0,pos=-1,m1,m2;bool**s=newbool*[n];//定義一個(gè)二維數(shù)組，用來(lái)判斷是否為同一類for(i=0;i<n;i++)s[i]=newbool[n];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)s[i][j]=true;//初始化數(shù)組elses[i][j]=false;}}while(k<n-1){for(i=0;i<n;i++){if(s[i][GE[k].fromvex]==1)m1=i;if(s[i][GE[k].endvex]==1)m2=i;}if(m1!=m2){//判斷是否為同一類,如果為同一類（該類中所有的點(diǎn)到起點(diǎn)和終//點(diǎn)的邊在s數(shù)組中賦為1），cur[++pos].fromvex=GE[k].fromvex;cur[pos].endvex=GE[k].endvex;cur[pos].weight=GE[k].weight;for(i=0;i<n;i++){if(s[m1][i]||s[m2][i])//把該點(diǎn)添加到該類，并和并兩個(gè)類 s[m1][i]=1;elses[m1][i]=0;s[m2][i]=0;}}k++;}for(i=0;i<n;i++){delete[]s[i];}}intmain(){inti,j;intnumVertex,numEdge;cout<<"請(qǐng)輸入點(diǎn)的個(gè)數(shù)和邊的條數(shù)："<<endl;cin>>numVertex>>numEdge;cout<<"請(qǐng)輸入邊的起始位置和邊的權(quán)值："<<endl;for(i=0;i<numEdge;i++)cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;for(i=0;i<numEdge;i++)for(j=i;j<numEdge;j++){if(GE[j].weight<GE[i].weight)//將邊的權(quán)值按從小到大排列swap(GE,i,j);}Kruskal(numEdge);for(i=0;i<numVertex-1;i++)cout<<cur[i].fromvex<<"->"<<cur[i].endvex<<":"<<cur[i].weight<<endl;system("pause");return0;}五．調(diào)試分析：將選邊的過(guò)程輸出來(lái)檢驗(yàn)算法的正確性。六．測(cè)試結(jié)果：七．實(shí)驗(yàn)心得：1、一開始我不會(huì)二維數(shù)組的動(dòng)態(tài)分配，這次通過(guò)查閱資料掌握了該方法，讓我學(xué)到了新知識(shí)。2、在一開始寫程序時(shí)，只是把一個(gè)點(diǎn)添加到一個(gè)類中。后來(lái)分析才改正錯(cuò)誤，將兩個(gè)集合進(jìn)行合并。3、曾試圖用兩個(gè)頂點(diǎn)是否有同一個(gè)根結(jié)點(diǎn)來(lái)判斷兩點(diǎn)是否為同一集合的，但未實(shí)現(xiàn)。八、附件最小生成樹問(wèn)題.cpp最小生成樹問(wèn)題.exe代碼：#include<iostream>usingnamespacestd;structG{intfromvex;intendvex;intweight;}GE[100],cur[100];voidswap(G*GE,inti,intj){//交換函數(shù)inttemp=GE[i].fromvex;GE[i].fromvex=GE[j].fromvex;GE[j].fromvex=temp;temp=GE[i].endvex;GE[i].endvex=GE[j].endvex;GE[j].endvex=temp;temp=GE[i].weight;GE[i].weight=GE[j].weight;GE[j].weight=temp;}voidKruskal(intn){inti,j,k=0,pos=-1,m1,m2;bool**s=newbool*[n];//定義一個(gè)二維數(shù)組，用來(lái)判斷是否為同//一類for(i=0;i<n;i++)s[i]=newbool[n];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)s[i][j]=true;//初始化數(shù)組elses[i][j]=false;}}while(k<n-1){for(i=0;i<n;i++){if(s[i][GE[k].fromvex]==1)m1=i;if(s[i][GE[k].endvex]==1)m2=i;}if(m1!=m2){//判斷是否為同一類,如果為//同一類（該類中所有的點(diǎn)到起點(diǎn)和終點(diǎn)的邊在s數(shù)組中賦為1），cur[++pos].fromvex=GE[k].fromvex;cur[pos].endvex=GE[k].endvex;cur[pos].weight=GE[k].weight;for(i=0;i<n;i++){if(s[m1][i]||s[m2][i])//把該點(diǎn)添加到該類，并和并兩個(gè)類 s[m1][i]=1;elses[m1][i]=0;s[m2][i]=0;}}k++;}for(i=0;i<n;i++){delete[]s[i];}}intmain(){inti,j;intnumVertex,numEdge;cout<<"請(qǐng)輸入點(diǎn)的個(gè)數(shù)和邊的條數(shù)："<<endl;cin>>numVertex>>numEdge;cout<<"請(qǐng)輸入邊的起始位置和邊的權(quán)值："<<endl;for(i=0;i<numEdge;i++)cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;for(i=0;i<numEdge;i++)for(j=i;j<numEdge;j++){if(GE[j].weight<GE[i].weight)