管道鋪設(shè)問(wèn)題

1、實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案一.問(wèn)題描述1.實(shí)驗(yàn)題目：需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間則可以鋪設(shè)管道，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，最小生成樹(shù)。2 .基本要求：在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū) 用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。3 .測(cè)試數(shù)據(jù)：使用卜圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。但由于地理環(huán)境不同，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的，又能使總投資最小。每條管道的費(fèi)I參考解:二.需求分析1 .程序所能達(dá)到的基本

2、可能：在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道， 則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同， 所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。2 .輸入輸出形式及輸入值范圍：程序運(yùn)行后，顯示提示信息：請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù)，邊數(shù)）之后程序從文件名為"C:data.txt讀入頂點(diǎn)信息和邊的信息，之后 顯示提示信息輸入開(kāi)始節(jié)點(diǎn)，執(zhí)行生成最小樹(shù)程序，輸出生成的最小樹(shù)信息。3 .測(cè)試數(shù)據(jù)要求：頂點(diǎn)數(shù)邊數(shù)為整數(shù)

3、，頂點(diǎn)信息為大寫(xiě)字母，邊的權(quán)值為浮點(diǎn)型，C:data.txt 文件內(nèi)容為：ABCDEFGHI1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 69 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.23541.1三.概要設(shè)計(jì)1.所用到得數(shù)據(jù)結(jié)構(gòu)及其ADTtypedef struct node/邊表結(jié)點(diǎn)int NO;II鄰接點(diǎn)域;vertexType adj vex;/ /EdgeType info; struct node *n ext;JEdgeNode;t

4、ypedef struct vnode(vertexType vertex; /EdgeNode *firstedge;/ JVertexNode;typedef struct/(VertexNode adjlistMaxVertexNum;int n,e;/JALGraph;/ ALGraph基本操作：ALGraph * CreateALGraph()2.主程序流程及其模塊調(diào)用關(guān)系1)主程序模塊權(quán)值指向下一個(gè)鄰接點(diǎn)的指針域頂點(diǎn)表節(jié)點(diǎn)頂點(diǎn)域編表頭指針鄰接表頂點(diǎn)數(shù)和邊數(shù)是以鄰接表方式存儲(chǔ)的圖類型/建表顯示主界面建表1生成最小樹(shù)k結(jié)束 建表模塊 ALGraph * CreateALGraph()開(kāi)

5、始最小生成樹(shù)模塊 void tree(ALGraph *G,i nt m)開(kāi)始sum=O;lowm=0;visitedm=O;J< s!=NULLlows->NO=s->info; s=s->next;s=G- >adjlistm.first edge;lowi=1000;teedi=m;min=1000;j=1JN輸出邊頂點(diǎn)信息s=G->adjlistk.firstedgesum+=min; visitedk=O;visitedj>0&&lowj<min/A s!=NULLmin=lowj;k=j；j+(visiteds->

6、;NO>0&as->info<lows->NOlows->NO=s->info;teeds->NO=k;函數(shù)調(diào)用笑系圖四、詳細(xì)設(shè)計(jì)1 .實(shí)現(xiàn)每個(gè)操作的偽碼，重點(diǎn)語(yǔ)句加注釋1)建表模塊ALGraph * CreateALGraph() /建表(int ij,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fope n( "C:data.txt"J廣)；打開(kāi)文件if(fp=NULL)/未找到文件(prin tf("Ca nn't open the file!n &

7、quot;)；ex計(jì)；)G=(ALGraph *)malloc(sizeof(ALGraph);printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))n");scanf("%d,%d",&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立頂點(diǎn)信息(G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;)for(k=1 ;k<=G->e;k+)(/ printf(,請(qǐng)輸入第1條邊的兩個(gè)端點(diǎn)序

8、號(hào)，輸入格式為：i,jn",k);/scanf("%d,%d",&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s=(EdgeNode *)malloc(sizeof(EdgeNode); t=(EdgeNode*)malloc(sizeof(EdgeNode); print"'請(qǐng)輸入第4條邊的對(duì)應(yīng)權(quán)值n”,k);fscanf(fp,"f”,&m);保存邊信息，以無(wú)向網(wǎng)方式s->NO=j;s->adjve

9、x=G->adjlistj.vertex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;fclose(fp);/ 關(guān)閉文件return G;)2)生成最小生成樹(shù)模塊void tree(ALGraph *G,int m)(float low100

10、;int teed100;int k,i,j;float min,sum=0;EdgeNode *s;lowm=0;visitedm=0;for(i=1 ;i<=G->n;i+)(lowi=1000;teedi=m;)s=G->adjlistm.firstedge;while(s!=NULL)數(shù)組初始化lows->NO=s->info;s=s->next;)for(i=1 ;i<G->n;i+)(min=1000;for(j=1 ;j<=G->n;j+)找到最小權(quán)值if(visitedj>0&&lowj<m

11、in)/ min=lowj；k=j；/標(biāo)記節(jié)點(diǎn))sum+=min;visitedk=O;s=G->adjlistk.firstedge;while(s!=NULL)(if(visiteds->NO>0&&s->info<lows->NO)/(lows->NO=s->info;teeds->NO=k;)s=s->next;)printfC,最佳鋪設(shè)方案W);for(i=1 ;iv=G->n;i+)輸出最小生成樹(shù)信息if(i!=m)printf("(%d,%d)%.2ft",i,teedi,low

12、i);printf(u 最小權(quán)值為:%.2fn'sum);)3)主函數(shù)模塊void main()(ALGraph *G;inti;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);printf("實(shí)驗(yàn)名稱：實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案printf("姓名：王亞文己）;找到最小權(quán)值n")；printf(“學(xué)號(hào)：031350102nH);An'*);printf("printf("程序運(yùn)行開(kāi)始，)p

13、rintf("Current local time and date:%s”,asctime(timeinfo);G=CreateALGraph();/ 建表printf("輸入開(kāi)始節(jié)點(diǎn)W);scanf("d”,&i);tree(Gj); 生成最小樹(shù)/printfALGraph(G);printf("nH);printf("Current local time and date:%s”,asctime(timeinfo);)五、調(diào)試分析1.設(shè)計(jì)與調(diào)試過(guò)程中遇到的問(wèn)題分析、體會(huì)1)一開(kāi)始對(duì)文件讀寫(xiě)操作不熟，采用從鍵盤(pán)輸出的方式驗(yàn)證正確與否

14、，對(duì)應(yīng)程序如下：int ij,k;float m;EdgeNode *s,*t;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))n");scanf("%d,%d",&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立頂點(diǎn)信息G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;)for(k=1 ;k&l

15、t;=G->e;k+) (printf("請(qǐng)輸入第1條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：iJ'n'k);scanf("d,%d”,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);printf(H請(qǐng)輸入第 4條邊的對(duì)應(yīng)權(quán)值n”,k);scanf("%f”,&m);保存邊信息，以無(wú)向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vertex;s->info=m;s-&

16、gt;next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;)return G;)對(duì)應(yīng)截屏如下：發(fā)現(xiàn)這種方式輸入耗時(shí)長(zhǎng)，而且在生成樹(shù)程序不正確時(shí)修改程序需要重復(fù)輸 入，較為麻煩PAS；號(hào) Hi二號(hào)疔|刃|.U:uPIMI目!I)輸入格式為. i-J輸入格式為：輸入格式為：i BvjNc輸入格:0

17、1邊的對(duì)應(yīng)權(quán)11B接遼接|?0S XAO C 44,60C3j2>5.9011)12-10<4.3>21.30<9,8)8.73<5.3>輸出彳&的鄰接點(diǎn)尺權(quán)值：E41-10G S&.46D0的鄰接點(diǎn)及權(quán)值，F(xiàn)?8_?()E67.30C衛(wèi)的鄰接點(diǎn)及權(quán)值,C41,1()G10.5RPF的鄰接點(diǎn)刃權(quán)值：I79-20E85.60DG的鄰菽點(diǎn)及權(quán)值：HC 56.46 EH兇鄰接點(diǎn)坡權(quán)值：I S.7B A 12.H1 CI的鄰接點(diǎn)尺權(quán)值：11 18.20 H 8.70 FPress anv kev to cont2».21.30 AB 5.9

18、0.22)為檢驗(yàn)所建立的無(wú)向網(wǎng)，編寫(xiě)了一個(gè)輸出函數(shù)，輸出各個(gè)頂點(diǎn)以及與該頂點(diǎn)相鄰的其他頂點(diǎn)以及對(duì)應(yīng)權(quán)值，輸出函數(shù)為void prin tfALGraph(ALGraph *G)/輸出表inti;EdgeNode *s;printf(H 輸出信息 n");for(i=1 ;i<=G->n;i+) printf("%c 的鄰接點(diǎn)及權(quán)值:nM,G->adjlisti.vertex); s=G->adjlisti.firstedge; while(s!=NULL)(printf("%c %.2f ”,s->adjvex,s>info);

19、s=s->next;)printf("nH);輸出測(cè)試截屏如下證明從文件讀寫(xiě)的與所需要建立的無(wú)向網(wǎng)相符fC:USERSADMINISTRATODESKTCPVCDebugsa.exeI字號(hào)./實(shí)三,管道南設(shè)施工的最佳方案031350102姓名。王亞文程序運(yùn)行開(kāi)始.Current local tine and date：Thn 請(qǐng)端人頂點(diǎn)喊和邊數(shù)（輸入格式為，Nnu 12 1S：29：12201s頂點(diǎn)數(shù),邊數(shù)）谿攵開(kāi)始節(jié)點(diǎn)1<9,8>8.90<6,9>79.20A的鄰接點(diǎn)及權(quán)值:<2.1>32.90<7,5)10.S0<3,2>

20、;5.90<8,1>12.10<4.3>21.30<9.8>8.70<G>3>41.19輸出信息118.20 H 12.18B的鄰接點(diǎn)及權(quán)值：CA 32.85日的鄰捂點(diǎn)及權(quán)值：E 41.10 G 56.4044.6021.3032.8044.60 B 5.90II休鄰接點(diǎn)及權(quán)值、，98.70 E 67.30的鄰接點(diǎn)及權(quán)值：21.30C 41el0 C 10.50F的鄰接點(diǎn)及權(quán)值：I 79.20 E 85606的鄰接點(diǎn)及權(quán)值：H 52.50 C 56.40H的鄰接點(diǎn)及權(quán)值：I 8.70 A 12.10I的鄰接點(diǎn)及權(quán)值： n 18.20 II

21、9.70 Current local tine85.6098.7010.5052.5079.20and date：Thu67.30Hov 12 15：29：122015ress any key to continue2.主要算法的時(shí)間復(fù)雜度分析六、使用說(shuō)明程序運(yùn)行后，顯示提示信息：請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù)，邊數(shù)）之后程序從文件名為" C:data.txt讀入頂點(diǎn)信息和邊的信息，之后顯示提示信息輸入開(kāi)始節(jié)點(diǎn)，執(zhí)行生成最小樹(shù)程序，輸出生成的最小樹(shù)信息。七、測(cè)試結(jié)果，,管道鋪設(shè)施工的最任方案 字號(hào),031357 R2lb： 3J = 44 2kllb家三序運(yùn)彳 丁千干始，Cu

22、rrent _L ocal time and dateiTliu MOM號(hào)裔入頂點(diǎn)數(shù)和邊數(shù)（輸入格式如頂點(diǎn)數(shù)，邊數(shù)）餐人開(kāi)始節(jié)點(diǎn)隈性鋪設(shè)方菜K±4>32-80<?,E>13.&G<3,2>5.?G<SA1>1£-10<4,3521.36<5,3>41.10v9,e?e .70最小權(quán)值為furrent local time and dateAThu Nov 12 15： 33=44 2B15 *ress anyp key to continue因?yàn)檫叺捻旤c(diǎn)信息是大寫(xiě)英文字母，一后來(lái)采用在定義時(shí)考慮多定義一個(gè)量

23、，原程序：邊表結(jié)點(diǎn)鄰接點(diǎn)域;3）這個(gè)程序遇到的第開(kāi)嫡關(guān)圖g題是在建表過(guò)程權(quán)值的ASCLL碼值，typedef stru施用不方便，指向下一個(gè)鄰接點(diǎn)的指針域nodevertexType adjvex;EdgeType info;struct node *n ext;JEdgeNode;邊表結(jié)點(diǎn)/"鄰接點(diǎn)域;修正后的程序?yàn)椋簍ypedef struct node(int NO;權(quán)值指向下一個(gè)鄰接點(diǎn)的指針域JEdgeNode;這樣多定義了一個(gè)量在后面的過(guò)程中會(huì)簡(jiǎn)單許多，其次書(shū)上給的程序是生成有向網(wǎng)的，-vertexType adjvex;EdgeType info;/開(kāi)始我是考慮的將邊輸入

24、兩邊，就是在循環(huán)時(shí)的終止條件設(shè)為k<=2*G->e ;這樣雖然能解決無(wú)向網(wǎng)問(wèn)題，但是一條邊重復(fù)輸入兩邊，較為麻煩，后期修正為：s->NO=j;s->adjvex=G->adjlistj.vertex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj

25、.firstedge=t;修正后的函數(shù)雖然語(yǔ)句較之前的多了 5句但在輸入時(shí)少輸了一半的邊信息。其次解決耗時(shí)最長(zhǎng)的一個(gè)錯(cuò)誤是在建表中，原程序：鄰接表typedef VertexNode AdjlistMaxVertexNum;typedef structAdj list adjlist;/int n,e;頂點(diǎn)數(shù)和邊數(shù)int n;int e;JALGraph;/ ALGraph是以鄰接表方式存儲(chǔ)的圖類型這個(gè)程序是抄的書(shū)上的，一開(kāi)始不覺(jué)得書(shū)上的程序會(huì)是錯(cuò)的，結(jié)果一直沒(méi)有看這個(gè)定義，在輸入邊的信息時(shí)循環(huán)次數(shù)總是不對(duì)，一直嘗試著改動(dòng)寫(xiě)的輸入信息，弄了一下午也沒(méi)有搞定這個(gè)問(wèn)題，于是去求助研究生學(xué)長(zhǎng)，下面是

26、研究生學(xué)長(zhǎng)發(fā)過(guò)來(lái)的郵件幫我指出錯(cuò)誤所在，看了學(xué)長(zhǎng)的這封郵件后，重新改了一下自己的程序，修正后的程序?yàn)閠ypedef struct / 鄰接表VertexNode adjlistMaxVertexNum;int n,e;/頂點(diǎn)數(shù)和邊數(shù)JALGraph;/ ALGraph是以鄰接表方式存儲(chǔ)的圖類型語(yǔ)句定義錯(cuò)謀，上聞?lì)}所在:結(jié)構(gòu)體ALGraph紅色標(biāo)記靜分)中jAdjlist昭1也爐 面沒(méi)有宇義Adjlist這個(gè)類率；I 解決方案：考慮在主函鞭main)中將全扃結(jié)榕體數(shù)組typedefVertexNodeAdjl(5tMaxVerteMNium;中數(shù)組名作為參數(shù)進(jìn)入ALGraph *CreateAL

27、Graph()町 ALGraph * CreatsALGraphfVertexNode * adjirst);將3adjW舌的訪惻方式史改為adjli$ti)G原因;該結(jié)構(gòu)體數(shù)組定義為全局結(jié)構(gòu)體 數(shù)紅無(wú)須通過(guò)ALGraph結(jié)構(gòu)佛播針G來(lái)訕鳳使用數(shù)組1S針VertewNode審mdjli眈方便程序修正后輸入正常了，就開(kāi)始進(jìn)入下一個(gè)階段生成最小樹(shù)的程序。3)在生成最小樹(shù)這個(gè)程序的編寫(xiě)中，開(kāi)始因?yàn)榫幊绦蚴窃诶蠋熤v解生成樹(shù)之前，所以一開(kāi)始是完全沒(méi)有地方下手，網(wǎng)上百度了一下如何生成最小樹(shù)，發(fā)現(xiàn)有兩種方法，Kruskal和prim算法，但研究生學(xué)長(zhǎng)這個(gè)適合用prim算法，Kruskal算法適合與邊稀疏的連

28、通圖求解最小生成樹(shù)，所以在編寫(xiě)時(shí)主要研究的是用prim算法，在編寫(xiě)prim算法時(shí)除了很多問(wèn)題，例如一開(kāi)始我并沒(méi)有在循環(huán)中寫(xiě)te6di=m;這句話，導(dǎo)致在最后輸出邊的信息時(shí)會(huì)有隨機(jī)數(shù)產(chǎn)生，截圖如下：<2r858993460>32.8Q20<7 5)1()5() I v3.2x.90<4,3>2L30 v5,3>41,16，|<8 r3589934G0>12.10v9,8>8.70 最小權(quán)值為二211,6想到隨機(jī)數(shù)產(chǎn)生可能是因?yàn)闆](méi)有賦值，所以加上teedi=m;這句話果然最后就輸出正確了，再次在輸出時(shí)，產(chǎn)生的結(jié)果中有重復(fù)的一個(gè)節(jié)點(diǎn)，<1,

29、1 >1000.00這個(gè)不應(yīng)該被輸出，所以考慮在輸出時(shí)加一個(gè)限制條件i f ( i ! = m ) 再次輸出就沒(méi)有了最佳鋪設(shè)方案tZ,l>J2-80<6f9>79-23(7.5>10.50<8,1>12,10<9,8)8,70矗 洞就)口乞 11 J中間編寫(xiě)時(shí)問(wèn)題不大，之前有看過(guò)prim算法的詳細(xì)介紹，所以在主思路上沒(méi)有太大的錯(cuò)誤，相對(duì)寫(xiě)起來(lái)也比 較順利。2)建立鄰接表的復(fù)雜度為0(n+e);Prim算法的時(shí)間復(fù)雜度為O(elogn);八、附錄#include <stdio.h>#include <malloc.h>#in

30、clude <stdlib.h>時(shí)表示未訪問(wèn)，C-3，D-4，E-5，F(xiàn)-6，G-7，H-8，1-9輸入序號(hào)與字母對(duì)應(yīng)關(guān)系A(chǔ)-1B-2#define MaxVertexNum 100 typedef char vertexType;typedef float EdgeType;邊表結(jié)點(diǎn)struct node /int NO; / vertexType adjvex;鄰接點(diǎn)域；EdgeType info;/struct node *next;/權(quán)值JEdgeNode;指向下一個(gè)鄰接點(diǎn)的指針域typedef struct vnode /頂點(diǎn)表節(jié)點(diǎn)vertexType vertex;/E

31、dgeNode *firstedge;頂點(diǎn)域/ JVertexNode;編表頭指針鄰接表int visited100; 訪問(wèn)變量，為一 typedeftypedef struct /VertexNode adjlistMaxVertexNum;頂點(diǎn)數(shù)和邊數(shù)int n,e;/是以鄰接表方式存儲(chǔ)的圖類型JALGraph;/ ALGraphALGraph * CreateALGraph()/建表intfloat m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=f。pen(”C:data.txtTr");打開(kāi)文件if(fp=NULL)/未找到文件(printf

32、("Cann't open the file!n"); exit(1);)G=(ALGraph *)malloc(sizeof(ALGraph);printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))nu);scanf(',%d,%d,&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立頂點(diǎn)信息(G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;for(k=1 ;k<=G->e;

33、k+)(/ printf(,1請(qǐng)輸入第% d條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：/scanf(H%d,%d",&i,&j);fscanf(fpcT,&i);fscanf(fp/d”,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode); t=(EdgeNode*)malloc(sizeof(EdgeNode);/ printf(u請(qǐng)輸入第% 4條邊的對(duì)應(yīng)權(quán)值n”,k);fscanf(fp,"R&m);保存邊信息，以無(wú)向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vert

34、ex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;)fclose(fp);/ 關(guān)閉文件return G;void tree(ALGraph *GJnt m) (float low100;int teed100;int kJJ;float min,s

35、um=0;EdgeNode *s;lowm=0;visitedm=0;for(i=1 ;i<=G->n;i+)(lowi=1000;teedi=m; s=G->adjlistm.firstedge; while(s!=NULL)/ 數(shù)組初始化lows->NO=s->info;s=s->next;for(i=1 ;i<G->n;i+)(min=1000;for(j=1 ;j<=G->n;j+)(if(visitedj>0&&lowj<min)/ 找到最小權(quán)值(min=lowj；k=j；/標(biāo)記節(jié)點(diǎn))sum+=m

36、in;visitedk=O;s=G->adjlistk.firstedge;while(s!=NULL)(if(visiteds->NO>0&&s->info<lows->NO)/ 找到最小權(quán)值( lows->NO=s->info;teeds->NO=k;)s=s->next;printf("最佳鋪設(shè)方案n");for(i=1 ;iv=G->n;i+)輸出最小生成樹(shù)信息if(i!=m)printf("(%d,%d)%.2ft"Ji,teedi,lowi);printf(&q

37、uot;最小權(quán)值為:%.2fn'sum);)/*void printfALGraph(ALGraph *G) / 輸出表int i;EdgeNode *s;printf("輸出信息 n”)；for(i=1 ;iv=G->n;i+)(printf("%c 的鄰接點(diǎn)及權(quán)值:n",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)(printf("%c %.2f ”,s->adjvex,s->info);s=s->next;)printf("nn);)7void main()(ALGraph *G;int i;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);pri