1、實習三求無向連通圖的生成樹1.需求剖析問題描繪:若要在n個城市之間建設通訊網絡，只要要架設n-1條路線即可。怎樣以最低的經濟代價建設這個通訊網，是一個網的最小生成樹問題。基本要求:(1)利用克魯斯卡爾算法求網的最小生成樹，此中，以課本8.7節中的等價類表示結構生成樹過程中的連通重量。(2)利用普里姆算法求網的最小生成樹。(3)以文本文件形式輸出生成樹中各條邊以及他們的權值。2.設計(1)設計思想：創立毗鄰矩陣儲存結構。本程序主要分為兩個模塊：創立鄰接矩陣模塊，最小生成樹模塊。創立毗鄰矩陣模塊：以毗鄰矩陣的儲存形式創立無向網。最小生成樹模塊：生成最小生成樹，輸出其各條邊及權值。(2)綱要設計：i

2、nt型LocateVex函數判斷權值在矩陣的地點；申明CraeteGraph函數創立毗鄰矩陣；申明kruskal函數用于生成最小生成樹；申明main函數為程序調用步驟。(3)設計詳盡：a.將程序分為兩個模塊：B.主函數流程圖：c.最小生成樹流程圖(4)調試剖析：-變量沒定義就使用解決：定義完變量在使用。-子函數嵌套定義；解決：子函數獨自定義，可調用。-使用數組是越界；解決：注意數組的值，注意不可以越界。(5)用戶手冊：a.主頁面：b.輸入極點數及邊數的信息：c.輸入極點信息：d.輸入極點及權值：(6)測試結果：輸出最小生成樹及權值：(7)源程序：#include#include#include

3、#defineMAX100#defineMAX_VERTEXNUM20typedefcharVertexMAX;/極點字符串typedefintAdjmatrixMAX_VERTEXNUMMAX_VERTEXNUM;/毗鄰矩陣typedefstruct/定義圖VertexvexsMAX_VERTEXNUM;Adjmatrixarcs;intvexnum,arcnum;MGraph;intLocateVex(MGraph*G,Vertexu)/判斷權值在矩陣的地點inti;for(i=0;ivexnum;+i)if(strcmp(G-vexsi,u)=0)returni;return-1;voi

4、dCreateGraph(MGraph*G)/創立毗鄰矩陣inti,j,k,w;Vertexva,vb;printf(請輸入極點數和邊數：（用空格分開）n);scanf(%d%d,&G-vexnum,&G-arcnum);printf(請輸入%d個極點的信息：（用空格分開）n,G-vexnum);for(i=0;ivexnum;+i)scanf(%s,G-vexsi);for(i=0;ivexnum;+i)for(j=0;jvexnum;+j)G-arcsij=MAX;printf(請輸入%d條邊的兩個極點及權值：（用空格分開）n,G-vexnum);for(k=0;karcnum;+k)sc

5、anf(%s%s%d*c,va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G-arcsij=G-arcsji=w;voidkruskal(MGraphG)/最小生成樹intsetMAX_VERTEXNUM,i,j;intk=0,a=0,b=0,min=G.arcsab;for(i=0;iG.vexnum;+i)seti=i;printf(最小生成樹的各條邊及權值為：n);while(kG.vexnum-1)for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)if(G.arcsijmin)min=G.arcsij;a=i;b=j;if(seta!=setb)printf(%s-%s-%dn,G.vexsa,G.vexsb,G.arcsab);k+;for(i=0;G.vexnum;i+)if(seti=setb)seti=seta;min=