数据结构课程设计报告蔡金林18031944一. 设计课题：管道铺设施工的最佳方案选择.N(N10)个居名之间需要铺设煤气管道.假设任意两个居名之间都可以铺设煤气管道，但代价不同事先将任意两个居需之间铺设煤气管道的代价存入磁盘文件中设计一个最佳方案使得这N个居名之间铺设煤气管道所需要代价最少，并希望以图形方式在屏幕上输出结果。二. 算法思想：要在N个城市之间铺设煤气管道，则连通N个城市只需要N1条线路.而每两个城市之间铺设管道都需要付出一定的经济代价.而在N个城市之间，最多可能铺设N(N-1)/2条管道，要在这些管道中选择N1条最少耗费的管道线路就可以转化为求最小生成树的问题一个生成数的代价就是树上各边的代价之合.构造最小生成树可以有多种算法其中多数算法利用了最小生成树的MST性质：假设ga=(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中I】eu,vEV-U,则必存在一棵包含边(u,v)的最小生成树.(证明略)普里姆Qmm)算法就是利用这个性质构造最小生成树的算法.假设ga=(V,E
