地鐵建設(shè)計(jì)算系統(tǒng).doc

#include#include#include#define MAX_VERTEX_NUM 20typedef float VRType;#define MAX_NAME 10 / 頂點(diǎn)字符串的最大長(zhǎng)度+1#define INFINITY FLT_MAXtypedef char VertexTypeMAX_NAME;/typedef int Status;typedef struct / 記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義 VertexType adjvex; VRType lowcost; minsideMAX_VERTEX_NUM;typedef struct VRType adj; / 頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1(是)或0(否)表示相鄰否； / 對(duì)帶權(quán)圖，則為權(quán)值類型 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; / 頂點(diǎn)向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum,arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) MGraph;int LocateVex(MGraph G,VertexType u) / 初始條件:圖G存在,u和G中頂點(diǎn)有相同特征 / 操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1 int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.vexsi)=0) return i; return -1; int minimum(minside SZ,MGraph G) / 求closedge.lowcost的最小正值 int i=0,j,k; float min; while(!SZi.lowcost) i+; min=SZi.lowcost; / 第一個(gè)不為0的值 k=i; for(j=i+1;j0) if(minSZj.lowcost) min=SZj.lowcost; k=j; return k; void CreateAN(MGraph &G) / 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無(wú)向網(wǎng)G。算法7.2 int i,j,k;float w; VertexType va,vb; printf(請(qǐng)輸入的頂點(diǎn)數(shù),邊數(shù):n); scanf(%d%d,&G.vexnum,&G.arcnum); printf(請(qǐng)依次輸入各個(gè)頂點(diǎn)的值:n); for(i=0;iG.vexnum;+i) / 構(gòu)造頂點(diǎn)向量 scanf(%s,G.vexsi); for(i=0;iG.vexnum;+i) / 初始化鄰接矩陣 for(j=0;jG.vexnum;+j) G.arcsij.adj=INFINITY; / 網(wǎng) printf(請(qǐng)依次輸入各條邊的頂點(diǎn)1 頂點(diǎn)2 權(quán)值:n); for(k=0;kG.arcnum;+k) scanf(%s%s%f%*c,va,vb,&w); / %*c吃掉回車符 i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij.adj=G.arcsji.adj=w; / 無(wú)向 / return true; void MiniSpanTree_PRIM(MGraph G,VertexType u) int i,j,k; float num=0; minside closedge; k=LocateVex(G,u); for(j=0;jG.vexnum;+j) if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj.adj; closedgek.lowcost=0; printf(最小代價(jià)生成樹的各條邊為:n); for(i=1;iG.vexnum;+i) / 選擇其余G.vexnum-1個(gè)頂點(diǎn) k=minimum(closedge,G); / 求出T的下一個(gè)結(jié)點(diǎn)：第K頂點(diǎn) printf(%s-%s)n,closedgek.adjvex,G.vexsk); / 輸出生成樹的邊 num+=closedgek.lowcost; closedgek.lowcost=0; / 第K頂點(diǎn)并入U(xiǎn)集 for(j=0;jG.vexnum;+j) if(G.arcskj.adjclosedgej.lowcost) / 新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊 strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj.adj; printf(所需建設(shè)的總里程為:%f kmnn,num); void main() MGraph G; CreateAN(G); MiniSpanTree_PRIM(G,G.vexs0); /*懷化區(qū) 順義區(qū) 19.38順義區(qū) 呂平區(qū) 36.81順義區(qū) 平谷區(qū) 44.43順義區(qū) 海淀區(qū) 33.76海淀區(qū) 石景山 13.89海淀區(qū) 同州區(qū) 33.73海淀區(qū) 宣武區(qū) 11.96石景山 同州區(qū) 49.49石景山 宣武區(qū) 23.01石景山 房山區(qū) 19.1