离散数学实验报告

1、离散数学实验报告姓 名：学 号：班 级：实验地点：实验时间：1 实验目的和要求运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下：八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？从到234567811.32.10.90.71.82.01.820.91.81.22.82.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.52 实验环境和工具实验环境：Windows 7 旗舰版工具：Dev-C+ 5.8.33 实验过程

2、开始3.1 算法流程图结束int i,j;MGraph g;float AMAXV10;g.vexnum;在屏幕上打印运行结果Aij=INF;J<g.vexnumYdispMat(g);prim(g,0);i=0;j=0;g.vexnum=8;NY表中数据赋值给AMAXV10i<g.vexnumN3.2 程序核心代码/油管铺设问题 Prim算法实现#include <iostream>#include<iomanip>using namespace std;#define MAXV 10#define INF 32767 /INF表示typedef int

3、InfoType;typedef structint no; /顶点编号 InfoType info; /顶点其他信息 VertexType; /顶点类型typedef struct /图的定义float edgesMAXVMAXV; /邻接矩阵 int vexnum; /顶点数 VertexType vexsMAXV; /存放顶点信息 MGraph; /图的邻接矩阵类型/*输出邻接矩阵g*/ void DispMat(MGraph g) int i,j; for (i=0;i<g.vexnum;i+) for (j=0;j<g.vexnum;j+) if (g.edgesij=I

4、NF) cout<<setw(6)<<"" else cout<<setw(6)<<g.edgesij; cout<<endl; void prim(MGraph g,int v) /从顶点V0出发，按Prim算法构造G的最小生成树 /输出最小生成树的每条边及其权值 float VlengthMAXV;int i, j, k;int cloestMAXV;float min;float sum = 0.0;for(i=0;i<g.vexnum;i+) Vlengthi=g.edgesvi; cloesti=v

5、; for(i=1;i<g.vexnum;i+) min=INF; /min为其中最大的一条边=MAXV for(j=0;j<g.vexnum;j+) /找n-1条边 if(Vlengthj!=0&&Vlengthj<min) min=Vlengthj; k=j; cout<<"连接油井<"<<cloestk+1<<","<<k+1<<">"<<"长度为:"<<min<<en

6、dl; sum+=min; Vlengthk=0; Vlengthcloestk=0;for(j=0;j<g.vexnum;j+) /选择当前代价最小的边 if(g.edgeskj!=0&&g.edgeskj<Vlengthj) Vlengthj=g.edgeskj; cloestj=k; cout<<"管道总长度为："<<sum<<endl; int main() int i,j,u=3; MGraph g; float AMAXV10; g.vexnum=8; for (i=0;i<g.vexnum;

7、i+) for (j=0;j<g.vexnum;j+) Aij=INF;A01=1.3; A02=2.1; A03=0.9;A04=0.7; A05=1.8; A06=2.0;A07=1.8; A12=0.9; A13=1.8;A14=1.2; A15=2.8; A16=2.3;A17=1.1; A23=2.6; A24=1.7;A25=2.5; A26=1.9; A27=1.0;A34=0.7; A35=1.6; A36=1.5;A37=0.9; A45=0.9; A46=1.1;A47=0.8; A56=0.6; A57=1.0;A67=0.5; for (i=0;i<g.ve

8、xnum;i+) for (j=0;j<g.vexnum;j+) Aji=Aij; for (i=0;i<g.vexnum;i+) /*建立图的邻接矩阵*/ for (j=0;j<g.vexnum;j+) g.edgesij=Aij; cout<<endl; cout<<"各油井间距离:n" DispMat(g); cout<<endl; cout<<"最优铺设方案:n" prim(g,0); cout<<endl; return 0;3.3 运行结果3.4 运行结果分析程序实现了输出需要铺设管道的油井编号，并给出了每条管道长度以及总长度，基本实现了题目要求。进一步优化，根据用户输入的任意网络的数据，在屏幕打印出管道连接的设计图纸。4 实验心得离散数学作为一门培养抽象思维、离