1、管道铺设施工的最佳方案 1 / 6 数据结构课程设计报告数据结构课程设计报告 管道铺设施工管道铺设施工 采用最小生成树算法采用最小生成树算法 管道铺设施工的最佳方案 2 / 6 目录目录 课程设计课题课程设计课题3 设计要求及分析设计要求及分析3 开发环境开发环境3 类的结构图类的结构图4 程序结构程序结构4 测试结果测试结果5 收获与体会收获与体会6 管道铺设施工的最佳方案 3 / 6 【一】【一】课程设计课题：课程设计课题： 管道铺设施工的最佳方案选择 【二】【二】设计要求及分析：设计要求及分析： 要求：要求： N(N10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设
2、煤气管道，但代价不同。要求事先任意两居民区之间铺设煤气管道的代价存入磁盘 文件中。设计一个最佳方案使得这 N 个居民区之间铺设煤气管道所需代价最小，并 将结果以图形方式在屏幕上输出。 MST性质性质：最小生成树具有 MST 性质，即，假设 G=（V，E）是一个无向连通图，U 是 顶点集 V 的一个非空子集。若（u,v）是一条具有最小权值的边，其中 uU,vV-U, 则必存在一颗包含边(u,v)的最小生成树。 Prim 算法算法：Prim 算法的基本思想是：设 G=(V ,E)是一个无向连通图，令 T=(U,TE)是 G 的 最小生成树。T 的初始状态为 U=v0(v0V),TE=.然后重复执行
3、下述操作：在所 有 uU，vV-U 的边中找一条代价最小的边(u,v)并入集合 TE，同时 v 并入 U，直 至 U=V 为止。此时 TE 中必有 n-1 条边，T 就是最小生成树。 显然 ，prim 算法的关键是图和找到链接 U 和 V-U 的最短边来扩充生成树 T。设当 前 T 中有 k 个顶点，则所有满足 uU,vV-U 的边最多有 k*(n-k)条，从如此大的边 集中选取最短边是不太经济的。 利用 MST 性质， 可以用下述方法构造候选最短边集： 对应 v-u 中的每个顶点，保留从该顶点到 U 中各顶点的最短边，取候选最短边集为 V-U 中 n-k 个顶点所关联的 n-k 条最短边的集
4、合。 需求分析需求分析:设计要求是选择管道铺设施工的最佳方案，则必须采用 prim 算法来选择出最佳 方案。且由于原始数据量较大，则需要使用读取磁盘文件的方法来读入数据。由于 在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接 矩阵存储；为了能访问邻接矩阵类中的私有成员变量，将 Prim 算法设为邻接矩阵的 成员函数。 而由于设计要求以图形方式在屏幕上输出， 则使用 MFC 将结果一图形方 式输出。 【三】【三】开发环境开发环境： 软件：Microsoft Visual Studio 2005 OS 名称 ：Microsoft Windows XP Professional 硬盘：160G 内存：1G 【四】四】类的结构
