最小生成樹實(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

醫(yī)院實(shí)習(xí)報(bào)告04-27

在銀行實(shí)習(xí)報(bào)告04-27

煤礦實(shí)習(xí)報(bào)告04-27

行業(yè)實(shí)習(xí)報(bào)告04-28

研究實(shí)習(xí)報(bào)告04-28

幼師的實(shí)習(xí)報(bào)告04-28

廣告實(shí)習(xí)報(bào)告04-29

體會(huì)實(shí)習(xí)報(bào)告05-04