离散数学实验报告.doc

离散数学实验报告姓名:学号:班级:实验地点:实验时间:实验目的和要求运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下:八口海上油井相互间距离如下表,其中1号井离海岸最近,为5km。问从海岸经1号井铺设油管把各井连接起来,怎样连油管长度最短(为便于检修,油管只准在油井处分叉)?从~:Windows7旗舰版工具:Dev-C++,j;MGraphg;floatA[MAXV][10];;在屏幕上打印运行结果A[i][j]=INF; J< YdispMat(g);prim(g,0);i=0;j=0;=8; N Y表中数据赋值给A[MAXV][10]i< N 程序核心代码//油管铺设问题Prim算法实现#include<iostream>#include<iomanip>usingnamespacestd;#defineMAXV10#defineINF32767//INF表示∞typedefintInfoType;typedefstruct{ intno;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct{//图的定义 floatedges[MAXV][MAXV];//邻接矩阵intvexnum;//顶点数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//图的邻接矩阵类型/*输出邻接矩阵g*/voidDispMat(MGraphg){inti,j;for(i=0;i<;i++){for(j=0;j<;j++)if([i][j]==INF)cout<<setw(6)<<"∞";elsecout<<setw(6)<<[i][j];cout<<endl;}}voidprim(MGraphg,intv){//从顶点V0出发,按Prim算法构造G的最小生成树//输出最小生成树的每条边及其权值 floatVlength[MAXV]; inti,j,k; intcloest[MAXV]; floatmin; floatsum=; for(i=0;i<;i++){ Vlength[i]=[v][i]; cloest[i]=v;}for(i=1;i<;i++){ min=INF;//min为其中最大的一条边=MAXV for(j=0;j<;j++){//找n-1条边 if(Vlength[j]!=0&&Vlength[j]<min){ min=Vlength[j]; k=j;}}cout<<"连接油井<"<<cloest[k]+1<<","<<k+1<<">"<<" 长度为:"<<min<<endl;sum+=min;Vlength[k]=0;Vlength[cloest[k]]=0; for(j=0;j<