實習三求無向連通圖的生成樹.doc

《實習三求無向連通圖的生成樹.doc》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

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

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

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

4、XNUM][MAX_VERTEXNUM];//鄰接矩陣typedefstruct//定義圖{Vertexvexs[MAX_VERTEXNUM];Adjmatrixarcs;intvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,Vertexu)//判斷權值在矩陣的位置{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("請輸入頂點數(shù)和邊數(shù)：（用空格隔開）");scanf("%d%d",&G->vexnum,&G->arcnum);printf("請輸入%d個頂點的信息：（用空格隔開）",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("請輸入%d條邊的兩個頂點及權值：（用空格隔開）

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、權值為：");while(k

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