- 相關推薦
最小生成樹實習報告 -實習報告
實習報告題目：停車場的管理班級：姓名：學號：完成日期：一.需求分析1.若要在n個城市之間建設同心網絡，只需要架設n-1條線路即可。以最低的經濟代價建設這個通信網。2.利用克魯斯卡爾算法求網的最小生成樹，抽象數(shù)據類型MFSet，以文本形式輸出生成樹各條邊及權值。3.測試數(shù)據見如下二.概要設計1.MFSet Graph{數(shù)據對象：vex1,wex2為圖的點數(shù)據關系：R={vex1,vex2|vex1,vex2∈N,vex1,vex2表示vex1到vex2的弧}基本操作：kruskal(Edge E,int n,int e)初始條件：E存在操作結果：對插入邊判定，生成最小生成樹order(Edge E,int n)初始條件：E數(shù)組存在操作結果：對E數(shù)組按權值排序}三.詳細設計#define MAXE 11#define MAXV 10#include stdio.h#include stdlib.h#include math.h typedef struct{int vex1；//邊的起始頂點int vex2；//邊的終止頂點int weight；//邊的權值}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；//表示當前構造最小生成樹的第k條邊，初值為1 j=0；//E中邊的下標，初值為0 while(k e)//生成的邊數(shù)小于e時繼續(xù)循環(huán){m1=E[j].vex1；m2=E[j].vex2；//取一條邊的兩個鄰接點sn1=vset[m1]；sn2=vset[m2]；//分別得到兩個頂點所屬的集合編號if(sn1！=sn2)//兩頂點分屬于不同的集合，該邊是最小生成樹的一條邊{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++)//兩個集合統(tǒng)一編號if(vset[i]==sn2)//集合編號為sn2的改為sn1 vset[i]=sn1；}//if j++；//掃描下一條邊}//while}//kruskal int order(Edge E,int 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("請輸入各邊及對應的的權值(起始頂點終止頂點權值)\n")；for(int i=0；i nume；i++){scanf("%d%d",&E[i].vex1,&E[i].vex2)；E[i].weight=rand()0；}//在這里對輸入的數(shù)據進行排序，達到假設的要求，即：假設數(shù)組E存放圖G中的//所有邊，且邊已按權值從小到大的順序排列order(E,nume)；kruskal(E,numn,nume)；}主程序order kruskal四.調試分析1.該程序使用一個額外的數(shù)組用于對邊能否成為生成樹邊進行判定，該方法很巧妙得讓程序的簡單明了。由于判定好后要對數(shù)組進行一次比較，所以時間和空間上有待優(yōu)化。2.該程序在對E數(shù)組進行排序時的時間復雜度為O(n),再對邊進行插入時的時間復雜度為O(n)3.程序在輸入時比較繁瑣，輸出的結果也不是很直觀，最好能改進成圖的形式輸出。五.用戶手冊1.本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為kruskal.exe 2.進入程序后顯示用戶界面：3.按提示輸入邊的頂點即可權值隨機生成，以回車符表示結束4.接受命令后執(zhí)行相應的算法生成最小生成樹并輸出六.測試結果E[0].vex1=1；E[0].vex2=3；E[4].vex1=1；E[4].vex2=
【最小生成樹實習報告 -實習報告】相關文章：
實習報告 -實習報告08-13
IT實習報告 -實習報告10-04
焊接實習報告 -實習報告07-24
實習報告2 -實習報告05-14
實習報告1 -實習報告05-27
護士實習報告 -實習報告10-04
實習報告5 -實習報告07-31
物流實習報告 -實習報告08-23
法律實習報告 -實習報告09-17
畢業(yè)實習報告 -實習報告06-16