高鐵修建最經(jīng)濟(jì)方案設(shè)計(jì)一、工程描述圖7-1所示的圖中頂點(diǎn)表示城市，邊表示兩個(gè)城市之間修建高鐵需要的費(fèi)用(單位：n億)，假設(shè)城市之間沒有修建任何高鐵，那么為了把n個(gè)城市連接起來(lái)，最多可修建n(n-l)/2條高鐵，最少可修建n-1條高鐵。如果考慮修建造價(jià)，而且還要保證每?jī)蓚€(gè)城市都可連通,那么如何選擇n-1條高鐵線路，使得修建高鐵的總造價(jià)最小呢？二、工程分析修建所有城市間高鐵的費(fèi)用預(yù)算后，為了降低本錢節(jié)省費(fèi)用，要設(shè)計(jì)最經(jīng)濟(jì)的建設(shè)方案,應(yīng)該盡量減少修建高鐵的條數(shù)，但又要保證所有城市.都能連通，那么必須修建n-1條高鐵線路，而且總費(fèi)用還要最低。在此我們通過(guò)普里姆方法生成最小生成樹來(lái)實(shí)現(xiàn)高鐵修建最經(jīng)濟(jì)方案。普里姆方法生成最小生成樹的過(guò)程如圖7-16所示，在此不再介紹具體過(guò)程。具體算法如下，首先，采用鄰接矩陣方法存儲(chǔ)圖，然后，定義一個(gè)輔助數(shù)組，用來(lái)存儲(chǔ)從U集合中某頂點(diǎn)出發(fā)到其他頂點(diǎn)邊上的權(quán)值，以及存儲(chǔ)該邊依附在U中的頂點(diǎn)下標(biāo)，最后，實(shí)現(xiàn)普里姆方法生成最小生成樹的算法。三、工程實(shí)現(xiàn)^include"stdio.h”ttdefincMAX1000〃單位百億元typedefstruct(charvcxs[10][8J;〃存放城市名稱，最多含10個(gè)城市intedges[l0][10];//存儲(chǔ)每條高鐵建設(shè)費(fèi)用intn,e;//分別代表圖的頂點(diǎn)數(shù)和邊數(shù)}Mgraph;structintlowcost;〃存儲(chǔ)該邊上的權(quán)值intvex;〃存儲(chǔ)該邊依附在U中的頂點(diǎn)下標(biāo)}CloseEdge[10];〃輔助數(shù)組〃創(chuàng)立高鐵建設(shè)網(wǎng)voidGreateMGraph(Mgraph*G)(inti,j,k,w;printfC請(qǐng)輸入城市個(gè)數(shù)和修建的高鐵條數(shù):")；scanfC%d,%d",&G->n,&G->e);for(i=0;i<G->n;i++)(printf("請(qǐng)輸入第%d個(gè)城市名稱:"，i+1);scanf("%s”,G~>vexs[i]);)printfC各城市序號(hào)為：\n");for(i=0;i<G~>n;i++)printf(，，%s:%d\t/，,G->vexs[i],i+1);printf("\n");for(i=0;i<G->n;i++)〃鄰接矩陣初始化(for(j=0;j<G->n;j++)G->edges[i][j]=MAX;〃假設(shè)建設(shè)費(fèi)用為最大G->edges[i][i]=0;〃到本身的費(fèi)用為0)for(k=0;k<G->e;k++)//建立鄰接矩陣(printf("請(qǐng)輸入建設(shè)第%d條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用：",k+1);scanf("%d,%d,",&i,&j,&w);//輸入邊的一對(duì)頂點(diǎn)序號(hào)G->edges[i-l][jT]=w;G->edges[j-l][iT]=w;}}〃求最小距離值，返回下標(biāo)intMinValue(intn)intj,k;for(j=0;j<n;j++)if(CloseEdge[j].lowcost>0)k=j;break;}for(j=0;j<n;j++)if(CloseEdgefj].lowcost〉0&&CloseEdge[j].lowcost<CloseEdge[k].lowcost)k=j;returnk;)〃普里姆方法構(gòu)建最小生成樹voidPrim(Mgraph*G,intu)(intcc=0,pp[20];//pp記錄最小生成樹中邊的下標(biāo)intk=0,i,j,si;for(i=0;i<G->n;i++)(CloscEdgc[i].vex=u;CloseEdge[i].lowcost=G->edges[u][i];}CloscEdgc〔u].lowcost=0;for(i=l;i<G->n;i++)〃最小生成樹的G->n-l條邊(k=MinValue(G~>n);sl=CloscEdge[k].vex;〃邊(si,k)是一條權(quán)值最小的邊CloseEdge[k].lowcost=0;//將頂點(diǎn)k加入到U中pp[cc++]=sl;pp[cc++]=k;for(j=0;j<G->n;j++)if(G->edges[k][j]<CloseEdge[j].lowcost)CloscEdgc[j].lowcost=G->edges[k][j];CloseEdgetj].vex=k;)}printfC?鐵建設(shè)最經(jīng)濟(jì)方案為:\n");for(i=0;i<2*(G->n-l);i=i+2)printfC應(yīng)建設(shè)高鐵:%s<=>%s,費(fèi)用:％d\n”,G->vexs[pp[i]],G->vexs[pp[i+1]],G->edges[pp[i]][pp[i+1]]);}main()(MgraphG;GreateMGraph(&G);Prim(&G,0);四、結(jié)果驗(yàn)證"0\李剛-味結(jié)構(gòu)'蓋教社出版\源代碼演7童圖的結(jié)構(gòu)分析與應(yīng)...叵）1請(qǐng)輸入城市個(gè)數(shù)和修建的高鐵條數(shù):5,8請(qǐng)輸入第1個(gè)城市名稱:A請(qǐng)輸入第2個(gè)城市名稱:B請(qǐng)輸入第3個(gè)城市名稱:C請(qǐng)輸入第4個(gè)城市名稱:D請(qǐng)輸入第5個(gè)城市名稱:E各撮市序號(hào)為：A:1B:2C:3D:4E:5請(qǐng)輸入建設(shè)第1條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用：1,2,5請(qǐng)輸入建設(shè)第2條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用:1,3,1請(qǐng)輸入建設(shè)第3條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用：1,4,6請(qǐng)輸入建設(shè)第4條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用:2,3,4請(qǐng)輸入建設(shè)第5條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用:3,4,7請(qǐng)輸入建設(shè)第6條高鐵兩個(gè)城市序號(hào)及建設(shè)費(fèi)用:3,5,3請(qǐng)輸入建設(shè)第7條高鐵兩個(gè)