課 程 設 計 報 告課程名稱 數據結構課程設計 題 目 最小通信網 指導教師 設計起始日期 5.25.9 學 院 計算機學院 系 別 計算機科學與工程 學生姓名 班級/學號 成 績 一、 需求分析 要在n個城市之間建立通信網，已知各個城市間的距離，建立的通信線路要使得這n個城市相連，而且建立的通信網絡代價最小。（1） 輸入：n個城市的距離關系圖，即圖的頂點和邊上的權值 （2） 輸出：含n個城市頂點的最小生成樹中的邊和代價（3） 功能：建立圖的最小生成樹（4） 測試數據：自選二、 概要設計1、 數據結構用圖來描述n個城市之間的關系，頂點為城市，邊位兩個城市間的代價2、 使用算法：采用prim算法算法思想：假設G=(V,E)為待求圖，其中V為圖中所有頂點的集合，E為帶權圖中所有帶權邊的集合。設置兩個新的集合U和TE，其中集合U用于存放G的最小生成樹中的頂點，集合TE存放G的最先生成樹的邊。令集合U的初值U=u1（假設構造最小生成樹時，頂點從u0出發），集合TE的初值為TE=。Prim算法的思想是，從所有uU，vV-U的邊中，選取具有最小權值的邊（u，v），將頂點v加入集合U中，將邊（u，v）加入集合TE中，如此不斷重復，直到U=V，最小生成樹樹構造完畢，這時集合TE中包含了最小生成樹的所有邊 Prim算法可用下述過程描述，其中用wuv表示頂點u與頂點v邊上的權值。（1）Uu1,T=; （2）while (UV)do (u，v)minwuv；uU，vVU TT(u，v) UUv （3）結束三、 詳細設計 1、數據結構詳細設計 圖的鄰接矩陣 typedef struct int Vnum;/*圖的頂點數*/ int ArcsMAXNMAXN;/*鄰接矩陣*/ Graph;/*圖的鄰接矩陣存儲法*/2、最小生成樹PRIM算法:在Prim算法中，應當考慮如何有效地找出滿足條件iU,jV-U，且權cij最小的邊(i,j)。實現這個目的的較簡單的辦法是設置2個一維數組closest和lowcost。Lowcostj中存儲iU,jV-U且權最小的邊(i,j)的權值cij，而closestj中存儲的是最小邊（i，j）的另一個端點i。在Prim算法執行過程中，先找出V-U中lowcost值最小的頂點j，然后根據數組closest選取邊(j,closestj)，最后將j添加到U中，并對其他closest和lowcost作必要的修改。偽算法如下：int prim(Graph G, int u) 1. u0= 起始點u; 2. for 每個結點v 3. 初始化距離數組Closest()和Lowcost() 4. for V-U中的頂點i 5. for 所有頂點j 6 k使Lowcost()最小的頂點 7. 將頂點k及邊(k,closest(k)加入MST中 8. for 所有頂點j 9. if 原Lowcost(j)c(k,j) 10. Lowcost(j)= c(k,j) 11. Clostest(j)=k 12. return MST一、 調試分析a調試過程中遇到的問題調試過程中出現了結果輸出錯誤問題，經過跟蹤調試發現是在修正Lowcost數組和Closest數組過程中數據未被修正，經改正后結果正確。b算法的時空分析算法中共四個for循環，第一個循環次數為n，第二個為n-1，第三個為n，第四個為n，并且第二個和第三、四個循環嵌套，所以循環次數為n的平方數量級。所以時間復雜度為O(n2)。算法中用到了兩個輔助一維數組closest和lowcost，數組的大小為n，即圖的頂點個數，所以算法的空間復雜度為O(n)。二、 程序清單1、圖的建立程序：作為圖的數據結構.#include#include#define MAXN 50#define INFINITY 32767 typedef struct int Vnum;/*圖的頂點數*/ int ArcsMAXNMAXN;/*鄰接矩陣*/ Graph;/*圖的鄰接矩陣存儲法*/ int create_graph(Graph *p)/*圖的創建,成功時返回非0值，失敗時返回0*/ int i,j,n; int v1,v2,w; char c; printf(nInput the vexnumber of graph:); scanf(%d,&n); if(nVnum=n; for(i=0;in;i+) for(j=0;jArcsij=0; else p-Arcsij=INFINITY; printf(nWill you input the weight of an edge?(y or n):); while(tolower(c=getchar()=y) printf(nedge(vertex1,vertex2,weight):); scanf(%d%d%d,&v1,&v2,&w); if(v1=0&v1=0&v2Arcsv1v2=p-Arcsv2v1=w; printf(nWill you continue to input the weight of an edge?(y or n):); return 1; 2、Prim算法：int prim(Graph G,int u0,int tree3)/*返回生成樹的代價,v是指定的起始頂點,生成樹的邊存放在數組tree中*/ int i,j,k,p,min,c; int lowcostMAXN,closestMAXN; for(i=0;iG.Vnum;i+) closesti=u0; /*初始時U中只有頂點v*/ lowcosti=G.Arcsu0i;/*U中頂點到V-U中頂點代價*/ c=0; /*記錄生成樹的代價*/ p=0; /*從序號為0的頂點出發求最小生成樹*/ for(i=0;iG.Vnum-1;i+)/*從圖中找出G.Vnum-1條邊，構成最小生成樹*/ min=INFINITY; for(j=0;jG.Vnum;j+) /*查找U中頂點到V-U中頂點的邊中權值最小者*/ /*(closestk,k)為找到的最小權值的邊*/ if(lowcostj!=0&lowcostjmin) min=lowcostj; k=j; treep0=closestk;/*存放找到的最小權值的邊*/ treep1=k; treep2=min; p+; c+=min;/*計算當前生成樹的代價*/ lowcostk=0;/*將k加入U*/ for(j=0;jG.Vnum;j+)/*更新V-U中與k鄰接的頂點到U中頂點的代價*/ if(G.Arcskj!=0&G.Arcskjlowcostj) lowcostj=G.Arcskj; closestj=k; return c;/*返回最小生成樹的代價*/ 3、測試程序：void main() int i; int treeMAXN3; int cost; Graph G; create_graph(&G); cost=prim(G,0,tree); printf(nMinimum-Cost spanning tree(prim):n); printf(edget weighttn); for(i=0;iG.Vnum-1;i+) printf(v%d,v%d)t %dn,treei0,treei1,treei2); printf(Cost:%dn,cost); 六、 使用說明和測試結果1、使用說明：首先用戶輸入圖