地铁建设问题_数据结构课程设计(编辑修改稿)

地铁建设问题_数据结构课程设计(编辑修改稿)内容摘要：

) { m=1。 k=i。 } if(m==1 amp。 amp。 a[i].lowcost!=0) { if(a[i].lowcosta[k].lowcost) k=i。 } } return k。 } 定位函数 int locatevex(Graph *g,char a[10]) //查找辖区 u 在辖区图中的位置 8 { int i。 for(i=0。 igvexnum。 i++)//循环执行条件是当 u=V[i]时停止，求 i 值 { if(strcmp(a,gV[i])==0) return i。 } if(i==gvexnum) return 1。 } 求最小生成树的结点算法 int minimun(struct tree *a,Graph g) //求出第 k 辖区， 此时 i 辖区与 k 辖区之间的距离最短 { int i,k,m=0。 for(i=0。 i。 i++) { if(m==0 amp。 amp。 a[i].lowcost!=0) { m=1。 k=i。 } if(m==1 amp。 amp。 a[i].lowcost!=0) 9 { if(a[i].lowcosta[k].lowcost) k=i。 } } return k。 } PRIM 算法 及输出 void MiniSpanTree_PRIM(Graph g,char a[10]) { struct tree closedge[M]。 int i,j,k,money=0。 k=locatevex(amp。 g,a)。 for(i=0。 i。 i++) { if(i!=k) { closedge[i].lowcost=[k][i]。 //两辖区 k， i 之间的距离 closedge[i].weizhi=k。 //与辖区 i 相邻的最近的辖区设为辖区 k } } closedge[k].lowcost=0。 //初始化， U={u} printf(********根据您的输入建立邻接表为 :********\n)。 10 for(i=0。 i。 i++) { for(j=0。 j。 j++) { printf(|%d| ,[i][j])。 } printf(\n\n)。 } printf(****得到应建设地铁的辖区及之间权值为 :****\n)。 for(i=1。 i。 i++) { k=minimun(closedge,g)。 //求出最小生成树 T 的下一个结点，第 k 结点 money+=closedge[k].lowcost。 printf(%d:%s %s %d\n,i,[closedge[k].weizhi],[k],closedge[k].lowcost)。 //输出生成树的边 closedge[k].lowcost=0。 //第 k 顶点并入 U 集 for(j=0。 j。 j++) { if([k][j]closedge[j].lowcost) //新顶点并入集后，选择新的边，将小的边放到辅助数组中 { closedge[j].weizhi=k。 closedge[j].lowcost=[k][j]。 } 11 } } printf(******据统计地铁的总建设路程为： %d *******\n,money)。 } 4,3,6 主函数模块 void main() { int i。 Graph g。 char a[10]。 i=creatgraph(amp。 g)。 if(i) { printf(***********请输入起始地点为： ************\n)。 scanf(%s,a)。 MiniSpanTree_PRIM(g,a)。 } printf(**********感谢使用本程序，谢谢。 *********\n)。 } 测试与分析 测试 测试数据： 12 3 为例 图 3 名称 ，如图 4 所示 ： 图 4 ，依次输入各个区域代号和边的权值，如图 5 所示： 图 5 13 ，输入地铁站的起始地点如图 6 所示： 图 6 ，如图 7 所示：。