實(shí)習(xí)三求無(wú)向連通圖的生成樹.doc

《實(shí)習(xí)三求無(wú)向連通圖的生成樹.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、實(shí)習(xí)三--求無(wú)向連通圖的生成樹————————————————————————————————作者：————————————————————————————————日期：實(shí)習(xí)三求無(wú)向連通圖的生成樹1.需求分析問(wèn)題描述:若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條路線即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問(wèn)題?；疽?(1)利用克魯斯卡爾算法求網(wǎng)的最小生成樹，其中，以課本8.7節(jié)中的等價(jià)類表示構(gòu)造生成樹過(guò)程中的連通分量。(2)利用普里姆算法求網(wǎng)的最小生成樹。(3)以文本文件形式輸出生成樹中各條邊以及他們的

2、權(quán)值。2.設(shè)計(jì)(1)設(shè)計(jì)思想：創(chuàng)建鄰接矩陣存儲(chǔ)結(jié)構(gòu)。本程序主要分為兩個(gè)模塊：創(chuàng)建鄰接矩陣模塊，最小生成樹模塊。創(chuàng)建鄰接矩陣模塊：以鄰接矩陣的存儲(chǔ)形式創(chuàng)建無(wú)向網(wǎng)。最小生成樹模塊：生成最小生成樹，輸出其各條邊及權(quán)值。(2)概要設(shè)計(jì)：int型LocateVex函數(shù)判斷權(quán)值在矩陣的位置；聲明CraeteGraph函數(shù)創(chuàng)建鄰接矩陣；聲明kruskal函數(shù)用于生成最小生成樹；聲明main函數(shù)為程序調(diào)用步驟。(3)設(shè)計(jì)詳細(xì)：a.將程序分為兩個(gè)模塊：B.主函數(shù)流程圖：c.最小生成樹流程圖(4)調(diào)試分析：--變量沒(méi)定義就使用解決：定義完變量在使用。--

3、子函數(shù)嵌套定義；解決：子函數(shù)單獨(dú)定義，可調(diào)用。--使用數(shù)組是越界；解決：注意數(shù)組的值，注意不能越界。(5)用戶手冊(cè)：a.主頁(yè)面：b.輸入頂點(diǎn)數(shù)及邊數(shù)的信息：c.輸入頂點(diǎn)信息：d.輸入頂點(diǎn)及權(quán)值：(6)測(cè)試結(jié)果：輸出最小生成樹及權(quán)值：(7)源程序：#include#include#include#defineMAX100#defineMAX_VERTEXNUM20typedefcharVertex[MAX];//頂點(diǎn)字符串typedefintAdjmatrix[MAX_VERTE

4、XNUM][MAX_VERTEXNUM];//鄰接矩陣typedefstruct//定義圖{Vertexvexs[MAX_VERTEXNUM];Adjmatrixarcs;intvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,Vertexu)//判斷權(quán)值在矩陣的位置{inti;for(i=0;ivexnum;++i){if(strcmp(G->vexs[i],u)==0)returni;}return-1;}voidCreateGraph(MGraph*G)//創(chuàng)建鄰接矩陣{inti,j

5、,k,w;Vertexva,vb;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：（用空格隔開(kāi)）");scanf("%d%d",&G->vexnum,&G->arcnum);printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的信息：（用空格隔開(kāi)）",G->vexnum);for(i=0;ivexnum;++i)scanf("%s",G->vexs[i]);for(i=0;ivexnum;++i)for(j=0;jvexnum;++j)G->arcs[i][j]=MAX;printf("請(qǐng)輸入%d條邊的兩個(gè)頂點(diǎn)及權(quán)值：（用空格隔開(kāi)）

6、n",G->vexnum);for(k=0;karcnum;++k){scanf("%s%s%d*c",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G->arcs[i][j]=G->arcs[j][i]=w;}}voidkruskal(MGraphG)//最小生成樹{intset[MAX_VERTEXNUM],i,j;intk=0,a=0,b=0,min=G.arcs[a][b];for(i=0;i

7、權(quán)值為：");while(k

8、.arcs[b][a]=MAX;}}}voidmain(){printf("歡迎建設(shè)通信網(wǎng)");MGraphG;CreateGraph(&G);kruskal(G);}