离散数学实验报告

离散数学 实验报告 离散数学实验报告 姓姓 名名 学学 号号 班班 级 级 实验地点实验地点 实验时间实验时间 离散数学 实验报告 1实验目的和要求实验目的和要求 运用最小生成树思想和求最小生成树程序解决实际问题 实际问题描述如下 八口海上油井相互间距离如下表 其中 1 号井离海岸最近 为 5km 问从海岸经 1 号井铺设油管把各井连接起来 怎样连油管长度最短 为便于检修 油管只准在油 井处分叉 从 到 2345678 11 32 10 90 71 82 01 8 20 91 81 22 82 31 1 32 61 72 51 91 0 40 71 61 50 9 50 91 10 8 60 61 0 70 5 2实验环境和工具实验环境和工具 实验环境 Windows 7 旗舰版 工具 Dev C 5 8 3 3实验过程实验过程 3 1 算法流程图算法流程图 Y N Y N 开始 int i j MGraph g float A MAXV 10 g vexnum i 0 j 0 g vexnum 8 i g vexnum J g vexnum A i j INF 表中数据赋值给 A MAXV 10 dispMat g prim g 0 在屏幕上打印运行 结果 结束 离散数学 实验报告 3 2 程序核心代码程序核心代码 油管铺设问题 Prim 算法实现 include include 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 g vexnum i for j 0 j g vexnum j if g edges i j INF cout setw 6 else cout setw 6 g edges 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 0 0 for i 0 i g vexnum i Vlength i g edges v i cloest i v 离散数学 实验报告 for i 1 i g vexnum i min INF min 为其中最大的一条边 MAXV for j 0 j g vexnum j 找 n 1 条边 if Vlength j 0 k j cout 连接油井 cloest k 1 k 1 长 度为 min endl sum min Vlength k 0 Vlength cloest k 0 for j 0 j g vexnum j 选择当前代价最小的边 if g edges k j 0 cloest j k cout 管道总长度为 sum endl 离散数学 实验报告 int main int i j u 3 MGraph g float A MAXV 10 g vexnum 8 for i 0 i g vexnum i for j 0 j g vexnum j A i j INF A 0 1 1 3 A 0 2 2 1 A 0 3 0 9 A 0 4 0 7 A 0 5 1 8 A 0 6 2 0 A 0 7 1 8 A 1 2 0 9 A 1 3 1 8 A 1 4 1 2 A 1 5 2 8 A 1 6 2 3 A 1 7 1 1 A 2 3 2 6 A 2 4 1 7 A 2 5 2 5 A 2 6 1 9 A 2 7 1 0 A 3 4 0 7 A 3 5 1 6 A 3 6 1 5 A 3 7 0 9 A 4 5 0 9 A 4 6 1 1 A 4 7 0 8 A 5 6 0 6 A 5 7 1 0 A 6 7 0 5 for i 0 i g vexnum i for j 0 j g vexnum j 离散数学 实验报告 A j i A i j for i 0 i g vexnum i 建立图的邻接矩阵 for j 0 j g vexnum j g edges i j A i j cout endl cout 各油井间距离 n DispMat g cout endl cout 最优铺设方案 n prim g 0 cout endl return 0 3 3 运行结果运行结果 离散数学 实验报告 3 4 运行结果分析运行结果分析 程序实现了输出需要铺设管道的油井编号 并给出了每条管道长度以及总长度 基 本实现了题目要求 进一步优化 根据用户输入的任意网络的数据 在屏幕打印出管 道连接的设计图纸 4实验心得实验心得 离散数学作为一门培养抽象思维 离散思维 程序化思维的一门学科