- 相關(guān)推薦
最小生成樹實(shí)習(xí)報(bào)告 -實(shí)習(xí)報(bào)告
實(shí)習(xí)報(bào)告題目:停車場(chǎng)的管理班級(jí):姓名:學(xué)號(hào):完成日期:一.需求分析1.若要在n個(gè)城市之間建設(shè)同心網(wǎng)絡(luò),只需要架設(shè)n-1條線路即可。以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)。2.利用克魯斯卡爾算法求網(wǎng)的最小生成樹,抽象數(shù)據(jù)類型MFSet,以文本形式輸出生成樹各條邊及權(quán)值。3.測(cè)試數(shù)據(jù)見如下二.概要設(shè)計(jì)1.MFSet Graph{數(shù)據(jù)對(duì)象:vex1,wex2為圖的點(diǎn)數(shù)據(jù)關(guān)系:R={vex1,vex2|vex1,vex2∈N,vex1,vex2表示vex1到vex2的弧}基本操作:kruskal(Edge E,int n,int e)初始條件:E存在操作結(jié)果:對(duì)插入邊判定,生成最小生成樹order(Edge E,int n)初始條件:E數(shù)組存在操作結(jié)果:對(duì)E數(shù)組按權(quán)值排序}三.詳細(xì)設(shè)計(jì)#define MAXE 11#define MAXV 10#include stdio.h#include stdlib.h#include math.h typedef struct{int vex1;//邊的起始頂點(diǎn)int vex2;//邊的終止頂點(diǎn)int weight;//邊的權(quán)值}Edge;void kruskal(Edge E,int n,int e){int i,j,m1,m2,sn1,sn2,k;int vset[MAXV];for(i=1;i=n;i++)//初始化輔助數(shù)組vset[i]=i;k=1;//表示當(dāng)前構(gòu)造最小生成樹的第k條邊,初值為1 j=0;//E中邊的下標(biāo),初值為0 while(k e)//生成的邊數(shù)小于e時(shí)繼續(xù)循環(huán){m1=E[j].vex1;m2=E[j].vex2;//取一條邊的兩個(gè)鄰接點(diǎn)sn1=vset[m1];sn2=vset[m2];//分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)if(sn1!=sn2)//兩頂點(diǎn)分屬于不同的集合,該邊是最小生成樹的一條邊{printf("(v%d,v%d):%d\n",m1,m2,E[j].weight);k++;//生成邊數(shù)增l if(k=e)break;for(i=1;i=n;i++)//兩個(gè)集合統(tǒng)一編號(hào)if(vset[i]==sn2)//集合編號(hào)為sn2的改為sn1 vset[i]=sn1;}//if j++;//掃描下一條邊}//while}//kruskal int order(Edge E,int n)//對(duì)邊進(jìn)行排序{int k;for(int i=0;i n;i++){for(int j=0;j n;j++){if(E[i].weight E[j].weight){k=E[i].vex1;E[i].vex1=E[j].vex1;E[j].vex1=k;k=E[i].vex2;E[i].vex2=E[j].vex2;E[j].vex2=k;k=E[i].weight;E[i].weight=E[j].weight;E[j].weight=k;}}}return 1;}int main(){Edge E[MAXE];int nume,numn;printf("輸入邊數(shù)和頂數(shù):\n");scanf("%d%d",&nume,&numn);//nume=10;//numn=6;printf("請(qǐng)輸入各邊及對(duì)應(yīng)的的權(quán)值(起始頂點(diǎn)終止頂點(diǎn)權(quán)值)\n");for(int i=0;i nume;i++){scanf("%d%d",&E[i].vex1,&E[i].vex2);E[i].weight=rand()0;}//在這里對(duì)輸入的數(shù)據(jù)進(jìn)行排序,達(dá)到假設(shè)的要求,即:假設(shè)數(shù)組E存放圖G中的//所有邊,且邊已按權(quán)值從小到大的順序排列order(E,nume);kruskal(E,numn,nume);}主程序order kruskal四.調(diào)試分析1.該程序使用一個(gè)額外的數(shù)組用于對(duì)邊能否成為生成樹邊進(jìn)行判定,該方法很巧妙得讓程序的簡(jiǎn)單明了。由于判定好后要對(duì)數(shù)組進(jìn)行一次比較,所以時(shí)間和空間上有待優(yōu)化。2.該程序在對(duì)E數(shù)組進(jìn)行排序時(shí)的時(shí)間復(fù)雜度為O(n),再對(duì)邊進(jìn)行插入時(shí)的時(shí)間復(fù)雜度為O(n)3.程序在輸入時(shí)比較繁瑣,輸出的結(jié)果也不是很直觀,最好能改進(jìn)成圖的形式輸出。五.用戶手冊(cè)1.本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng),執(zhí)行文件為kruskal.exe 2.進(jìn)入程序后顯示用戶界面:3.按提示輸入邊的頂點(diǎn)即可權(quán)值隨機(jī)生成,以回車符表示結(jié)束4.接受命令后執(zhí)行相應(yīng)的算法生成最小生成樹并輸出六.測(cè)試結(jié)果E[0].vex1=1;E[0].vex2=3;E[4].vex1=1;E[4].vex2=4;E[6].vex1=2;E[6].vex2=3;E[2].vex1=2;E[2].vex2=5;E[5].vex1=3;E[5].vex2=4;E[3].vex1=3;E[3].vex2=6;E[1].vex1=4;E[1].vex2=6;輸出v2,v3:1 v1,v2:24 v1,v4:34 v3,v5:58 v3,v6:62七.附錄由函數(shù)寫在同一文件下,無其他源程序文件名MSN空間完美搬家到新浪博客!【最小生成樹實(shí)習(xí)報(bào)告 -實(shí)習(xí)報(bào)告】相關(guān)文章:
實(shí)習(xí)生實(shí)習(xí)報(bào)告03-10
實(shí)踐實(shí)習(xí)報(bào)告04-27
煤礦實(shí)習(xí)報(bào)告04-27
研究實(shí)習(xí)報(bào)告04-28
廣告實(shí)習(xí)報(bào)告04-29