管道铺设用地征收

实验三：管道铺设施工的最佳方案

一、问题描述1.实验题目：

需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。

2.基本要求：

在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。

3.测试数据：

使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。

a38.244.618.28.7112.ib5.9ch52.541.1.379.256.4g10.585.667.3d参考解：21e98.7f

ai.32b5.988.h7c41.1egd二、需求分析

1.程序所能达到的基本可能：2110.5f

在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。

2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数，边数）之后程序从文件名为”c：\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。

3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，c：\data.txt文件内容为：abcdefghi1232.8235.91344.63421.34567.34698.75685.65710.53756.46979.27852.51812.1898.71918.23541.1三、概要设计

1.所用到得数据结构及其adttypedefstructnode//边表结点{intno;//邻接点域;vertextypeadjvex;.379.2.112edgetypeinfo;//权值

structnode*next;//指向下一个邻接点的指针域

}edgenode;

typedefstructvnode//顶点表节点{vertextypevertex;//顶点域edgenode*firstedge;//编表头指针

}vertexnode;

typedefstruct//邻接表{vertexnodeadjlist[maxvertexnum];intn，e;//顶点数和边数

}algraph;//algraph是以邻接表方式存储的图类型基本操作：algraph*createalgraph//建表2.主程序流程及其模块调用关系1）主程序模块

开始显示主界面建表生成最小树结束