管道铺设问题模板.doc

管道铺设问题实验三::需要在某个城市n个居民小区之间铺设煤气管道,则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则能够铺设管道,但由于地理环境不同,所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小,这个问题即为求无向网的最小生成树。基本要求:在可能假设的m条管道中,选取n-1条管道,使得既能连通n个小区,又能使总投资最小。每条管道的费用以网中该边的权值形式给出,网的存储采用邻接表的结构。测试数据:使用下图给出的无线网数据作为程序的输入,求出最佳铺设方案。参考解::在某个城市n个居民小区之间铺设煤气管道,则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则能够铺设管道,但由于地理环境不同,所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小,在可能假设的m条管道中,选取n-1条管道,使得既能连通n个小区,又能使总投资最小。:程序运行后,显示提示信息:请输入顶点数和边数(输入格式为:顶点数,边数)之后程序从文件名为”C:\\,之后显示提示信息输入开始节点,执行生成最小树程序,输出生成的最小树信息。:顶点数边数为整数,顶点信息为大写字母,边的权值为浮点型,C:\\://边表结点{ intNO;//邻接点域; vertexTypeadjvex; EdgeTypeinfo;//权值 structnode*next;//指向下一个邻接点的指针域}EdgeNode;typedefstructvnode//顶点表节点{ vertexTypevertex;//顶点域 EdgeNode*firstedge;//编表头指针}VertexNode;typedefstruct//邻接表{ VertexNodeadjlist[MaxVertexNum]; intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型基本操作:ALGraph*CreateALGraph()//建表主程序流程及其模块调用关系主程序模块建表模块ALGraph*CreateALGraph()最小生成树模块voidtree(ALGraph*G,intm)函数调用关系图四、,重点语句加注释1)建表模块ALGraph*CreateALGraph()//建表{ inti,j,k; floatm; FILE*fp; EdgeNode*s,*t; ALGraph*G; fp=fopen("C:\\","r");//打开文件 if(fp==NULL)//未找到文件 { printf("Cann'topenthefile!\n"); exit(1); }G=(ALGraph*)malloc(sizeof(ALGraph)); printf("请输入顶点数和边数(输入格式为:顶点数,边数)\n"); scanf("%d,%d",&G->n,&G->e); for(i=1;i<=G->n;i++)//建立顶点信息 { G->adjlist[i].vertex=fgetc(fp); G->adjlist[i].firstedge=NULL; visited[i]=i; } for(k=1;k<=G->e;k++) { // printf("请输入第%d条边的两个端点序号,输入格式为:i,j\n",k); // scanf("%d,%d",&i,&j); fscanf(fp,"%d",&i); fscanf(fp,"%d",&j);