最小生成樹課程設(shè)計(jì)

1、<p>　　數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)</p><p><b>　　說(shuō) 明 書</b></p><p>　　2013 年12月 20 日</p><p><b>　　需求分析</b></p><p>　　設(shè)計(jì)內(nèi)容：給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用prim算法或kruskal算法建立最小生成

2、樹，并計(jì)算得到的最小生成樹的代價(jià)。</p><p><b>　　基本要求：</b></p><p>　?。?）城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價(jià)；</p><

3、;p>　?。?）表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個(gè)城市，10條邊）；</p><p>　?。?）最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價(jià)。 </p><p>　　2本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)</p><p>　　本程序設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)為圖。</p><p><b>　　3 設(shè)計(jì)思想</b>&

4、lt;/p><p><b>　　普里姆算法</b></p><p><b>　　4 核心代碼</b></p><p>　　int main() //主函數(shù)</p><p>　　{ mgraph g; vertextype u; int k; </p><p>　　cre

5、ateUDN(&g); /* 生成鄰接矩陣結(jié)構(gòu)的圖 */</p><p>　　printf("\nThe graph is:\n");</p><p>　　print(g); /*輸出鄰接矩陣*/</p><p>　　printf("input the city you want to start:

6、");</p><p>　　scanf("%s",u); /* 輸入最小生成樹的起點(diǎn) */</p><p>　　k=locatedvex(g,u);</p><p>　　while(k==-1){</p><p>　　printf("the name of the city is wrong!

7、\n");</p><p>　　printf("input the city you want to start again:");</p><p>　　scanf("%s",u);</p><p>　　k=locatedvex(g,u);</p><p><b>　　}</b

8、></p><p>　　minispantree(g,u); /* 普里姆算法求最小生成樹 */</p><p><b>　　}</b></p><p><b>　　4 代碼</b></p><p>　　#include"stdio.h"</p><p

9、>　　#include"string.h"</p><p>　　#define maxnum 20 /* 圖的最大頂點(diǎn)數(shù) */</p><p>　　#define INFINITY 1000 /* 定義一個(gè)權(quán)值的最大值 */</p><p>　　typedef char vertextype[20];

10、 /*定義城市名稱*/</p><p>　　typedef struct arccell</p><p><b>　　{</b></p><p>　　int adj; /*弧的權(quán)值*/</p><p>　　int *info; /*弧上相關(guān)信息的指針*/</p><p

11、><b>　　}arccell;</b></p><p>　　typedef struct array</p><p><b>　　{</b></p><p>　　vertextype adjvex; /*頂點(diǎn)的鄰接點(diǎn)*/</p><p>　　int lowcost;

12、 /* 某頂點(diǎn)與已構(gòu)造好的部分生成樹的頂點(diǎn)之間的最小權(quán)值 */</p><p><b>　　}array;</b></p><p>　　typedef struct{ </p><p>　　vertextype vexs[maxnum]; /*頂點(diǎn)向量*/</p><p>　　arccell a

13、rcs[maxnum][maxnum]; /*鄰接矩陣*/</p><p>　　int vexnum,arcnum; /*圖的頂點(diǎn)個(gè)數(shù)和弧個(gè)數(shù)*/</p><p>　　array closedge[maxnum]; /* 用普里姆算法求最小生成樹時(shí)的輔助數(shù)組 */ </p><p><b>　　}</b>

14、</p><p><b>　　mgraph;</b></p><p>　　void createUDN(mgraph *g)</p><p><b>　　{ </b></p><p>　　/* 用鄰接矩陣構(gòu)造n個(gè)城市間的距離網(wǎng)g */</p><p>　　int i,j

15、,m,n,k,a,b,c;</p><p>　　vertextype x,y;</p><p>　　printf("input the number of cities (at least 6 cities) :"); </p><p>　　scanf("%d",&g->vexnum); /

16、* 輸入城市的個(gè)數(shù)（圖的頂點(diǎn)數(shù)） */</p><p>　　printf("input the number of roads (at least 10 roads):");</p><p>　　scanf("%d",&g->arcnum); /* 輸入道路的邊數(shù)（圖的邊數(shù)） */</p><p&g

17、t;　　printf("input the name of %d cities :",g->vexnum);</p><p>　　for(i=0;i<g->vexnum;i++)</p><p>　　scanf("%s",g->vexs[i]); /* 輸入城市名稱（圖的頂點(diǎn)） */</p>&l

18、t;p>　　for(m=0;m<g->vexnum;m++){</p><p>　　for(n=0;n<g->vexnum;n++)</p><p>　　g->arcs[m][n].adj=INFINITY;} /* 初始化鄰接矩陣 */</p><p>　　for(k=0;k<g->arcnum;k++){<

19、;/p><p>　　printf("input the distance of a road :");</p><p>　　scanf("%s%s%d",x,y,&c); /* 輸入城市間的距離（圖中邊的起點(diǎn)和終點(diǎn)及權(quán)值） */</p><p>　　a=locatedvex(*g,x);</p>&

20、lt;p>　　b=locatedvex(*g,y);</p><p>　　while(a==-1||b==-1){</p><p>　　printf("the name of the city is wrong!\n");</p><p>　　printf("input the distance of a road again :

21、");</p><p>　　scanf("%s%s%d",x,y,&c); </p><p>　　a=locatedvex(*g,x);</p><p>　　b=locatedvex(*g,y);</p><p><b>　　}</b></p><p>　　g

22、->arcs[a][b].adj=c;</p><p>　　g->arcs[b][a]=g->arcs[a][b];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void print(mgraph g)

23、/*輸出用鄰接矩陣構(gòu)造的n個(gè)城市間距離網(wǎng)g*/</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for (i=0;i<g.vexnum;i++)</p><p>　　{for(j=0;j<g.vexnum;j++)<

24、/p><p>　　printf("%-4d ",g.arcs[i][j].adj);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　voi

25、d minispantree(mgraph g,vertextype x){ /* 從第k個(gè)頂點(diǎn)出發(fā)構(gòu)造圖g的最小生成樹 */</p><p>　　int i,j,t,k,sum=0;</p><p>　　k=locatedvex(g,x);</p><p>　　for(j=0;j<g.vexnum;j++) /*輔助數(shù)組初始化*/&

26、lt;/p><p>　　if(j!=k) { g.closedge[j].lowcost=g.arcs[k][j].adj;</p><p>　　strcpy(g.closedge[j].adjvex,x);</p><p>　　} </p><p>　　g.closedge

27、[k].lowcost=0; /* 初始，U={u} */</p><p>　　for(i=1;i<g.vexnum;i++){ /* 選擇其余的G->vexnum-1個(gè)頂點(diǎn) */</p><p>　　k=min(g); /* 求出生成樹的下一個(gè)頂點(diǎn) */</p><p>　　print

28、f("(%s,%s) %d\n",g.closedge[k].adjvex,g.vexs[k],g.closedge[k].lowcost); /* 輸出生成樹的邊和權(quán)值 */</p><p>　　sum+=g.closedge[k].lowcost; /*計(jì)算最小生成樹的代價(jià)*/</p><p>　　g.closedge[k].lowcost=0;

29、 /* 第k頂點(diǎn)并入U(xiǎn)集 */</p><p>　　for(t=0;t<g.vexnum;t++) /* 新頂點(diǎn)并入U(xiǎn)后，修改輔助數(shù)組*/</p><p>　　if(g.arcs[k][t].adj<g.closedge[t].lowcost){</p><p>　　strcpy(g.closedge[t].adjve

30、x,g.vexs[k]);</p><p>　　g.closedge[t].lowcost=g.arcs[k][t].adj;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("The shortest distance i

31、s %d\n",sum); /*輸出最小生成樹的代價(jià)*/</p><p><b>　　}</b></p><p>　　int min(mgraph g){ /* 在輔助數(shù)組g.closedge[i]中選擇權(quán)值最小的頂點(diǎn)，并返回其位置 */</p><p>　　int i,a=0,min;</p>

32、<p>　　min=maxnum;</p><p>　　for(i=1;i<g.vexnum;i++)</p><p>　　if(g.closedge[i].lowcost<min&&g.closedge[i].lowcost!=0){</p><p><b>　　a=i;</b></p>

33、<p>　　min=g.closedge[i].lowcost;</p><p><b>　　}</b></p><p>　　return a;</p><p><b>　　}</b></p><p>　　int locatedvex(mgraph g,vertextype u){ /

34、*確定任一城市在距離網(wǎng)g中的位置*/</p><p><b>　　int i;</b></p><p>　　for(i=0;i<g.vexnum;i++)</p><p>　　if(strcmp(u,g.vexs[i])==0)</p><p><b>　　return i;</b></

35、p><p>　　return -1;</p><p><b>　　}</b></p><p>　　int main()</p><p>　　{ mgraph g; vertextype u; int k; </p><p>　　createUDN(&g); /* 生成鄰接矩陣

36、結(jié)構(gòu)的圖 */</p><p>　　printf("\nThe graph is:\n");</p><p>　　print(g); /*輸出鄰接矩陣*/</p><p>　　printf("input the city you want to start:");</p><p>　

37、　scanf("%s",u); /* 輸入最小生成樹的起點(diǎn) */</p><p>　　k=locatedvex(g,u);</p><p>　　while(k==-1){</p><p>　　printf("the name of the city is wrong!\n");</p><p>

38、;　　printf("input the city you want to start again:");</p><p>　　scanf("%s",u);</p><p>　　k=locatedvex(g,u);</p><p><b>　　}</b></p><p>　　min

39、ispantree(g,u); /* 普里姆算法求最小生成樹 */</p><p><b>　　}</b></p><p><b>　　5 程序運(yùn)行結(jié)果</b></p><p><b>　　8 心得體會(huì)</b></p><p>　　本次課程設(shè)計(jì)我們經(jīng)歷了最短時(shí)間最繁重的設(shè)計(jì)任

40、務(wù)，作為兩人組的課程設(shè)計(jì)任務(wù)難度相對(duì)來(lái)說(shuō)較大，我和我的合作伙伴盡了最大的努力來(lái)做到課程設(shè)計(jì)的要求，仍然不是很滿意最后的結(jié)果。但是，總的來(lái)說(shuō)也讓我們體會(huì)到了一些軟件開發(fā)的辛苦，有時(shí)候你確實(shí)需要在有限的時(shí)間內(nèi)來(lái)完成任務(wù)。最后本次課程任務(wù)教給我們很多，讓我們客觀的正視了自己一個(gè)學(xué)期的學(xué)習(xí)成果。我們相信自己通過這樣的任務(wù)能學(xué)到我們平時(shí)僅僅上課所學(xué)不到的知識(shí)，并發(fā)現(xiàn)、體會(huì)到了一種經(jīng)過辛苦編程，糾正代碼后所獨(dú)有的快樂。也讓我們發(fā)現(xiàn)了自己對(duì)于編程所潛