管道铺设施工的最佳方案问题VIP专享

一．问题描述：1.实验题目:需要在某个城市 n 个居民小区之间铺设煤气管道，则在这 n 个居民小区之间只需要铺设 n—1 条管道即可。假设任意两个小区之间都可以铺设管道,但由于地理环境不同，所需要的费用也不尽相同.选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2.基本要求：在可能假设的 m 条管道中，选取 n—1 条管道，使得既能连通 n 个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采纳邻接表的结构。3.测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解.4.简述每一部分的对象、目的和要求：I.主函数部分：对象:图 G;目的：为图 G 分配空间，以作为后续调用函数的参数；要求：无。II. Create_ALGraph（ ）函数部分：对象:顶点，边及其权值；目的:将顶点,边存放在一起，构成图;要求：构造顶点表,各顶点的邻接表以构造图.III。 Create_WLGraph（ ）函数部分：对象:图 G；目的:将图中的权值只存放一次，存放到 w 指向的结构体中；要求：权值只存放一次，再分别存放该边的左右顶点.IV。 select_info（ ）函数部分：对象:w 指向的结构体；目的：将该结构体中的各权值以升序排列；要求:采纳简单选择法进行排序。V. Create_TLGraph（ )函数部分:对象:排序后的 w 指向的结构体;目的:找到构成最小生成树的边；要求:依权值升序排列，推断各边是否构成回路来取舍各边。二．需求分析1.程序所能达到的基本可能：在 n 个小区 m 条管道中，选取 n-1 条管道，实现连通这 n 个小区,同时权值之和为最小.2.输入输出形式及输入值范围:程 序 运 行 后 , 用 户 可 根 据 提 示 信 息 ： ” Please input the vertices and the edges:"输入顶点数和边数，再根据提示信息：”Please input the information of the vertices："和”Please input the information of weight：”依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果.输入值必须为字母和浮点数，可以不必区分大小写。3.测试数据要求：用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式,有针对性...