离散数学实验报告.doc

离散数学实验报告
姓名:
学号:
班级:
实验地点:
实验时间:
实验目的和要求
运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下:
八口海上油井相互间距离如下表,其中1号井离海岸最近,为5km。问从海岸经1号井铺设油管把各井连接起来,怎样连油管长度最短(为便于检修,油管只准在油井处分叉)?
从~到
2
3
4
5
6
7
8
1







2






3





4




5



6


7

实验环境和工具
实验环境:Windows 7 旗舰版
工具:Dev-C++
实验过程
开始
算法流程图
结束
int i,j;
MGraph g;
float A[MAXV][10];;
在屏幕上打印运行结果
A[i][j]=INF;

J<
Y
dispMat(g);
prim(g,0);
i=0;
j=0;
=8;
N
Y
表中数据赋值给A[MAXV][10]
i<
N


程序核心代码
//油管铺设问题 Prim算法实现
#include <iostream>
#include<iomanip>
using namespace std;
#define MAXV 10
#define INF 32767 //INF表示∞
typedef int InfoType;
typedef struct{
int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct{ //图的定义
float edges[MAXV][MAXV]; //邻接矩阵
int vexnum; //顶点数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型
/*输出邻接矩阵g*/
void DispMat(MGraph g){
int i,j;
for (i=0;i<;i++){
for (j=0;j<;j++)
if ([i][j]==INF)
cout<<setw(6)<<"∞";
else
cout<<setw(6)<<[i][j];
cout<<endl;
}
}

void prim(MGraph g,int v){ //从顶点V0出发,按Prim算法构造G的最小生成树
//输出最小生成树的每条边及其权值
float Vlength[MAXV];
int i, j, k;
int cloest[MAXV];
float min;
float sum = ;
for(i=0;i<;i++){
Vle