數(shù)據(jù)結構C言語版本課程設計報告最小生成樹的應用

1、計算機系課程設計報告武 夷 學 院 課程設計報告課程名稱：數(shù)據(jù)結構（c言語版本）設計題目：最小生成樹的應用學生班級：10計科1班學生姓名：指導教師：完成日期：2012-01-05 計算機系課程設計報告 課程設計項目研究報告目錄一、問題描述及基本要求1 -二、 實現(xiàn)本程序需要解決的問題如下1 -三、 測試數(shù)據(jù)2 -四、 算法思想3 -五、 模塊劃分4 -六、 算法設計與分析7 -七、 源程序11 -八、 測試數(shù)據(jù)14 -九、 課程設計項目進度表及任務分配表及任務分配表15 -十、 設計心得16 -十一 參考文獻17 -計算機系課程設計報告一、為題描述及基本要求在n個城市間建立通信網(wǎng)絡，需架設n-

2、1條線路。求解如何以最低經(jīng)濟代價建設此通信網(wǎng)，這是一個最小生成樹問題。要求：（1）利用普利姆算法求網(wǎng)的最小生成樹；（2）輸出生成樹中各邊及權值。 二、實現(xiàn)本程序需要解決的問題如下(1)、如何選擇存儲結構去建立一個帶權網(wǎng)絡。(2)、如何在所選存儲結構下輸出這個帶權網(wǎng)絡。(3)、如何實現(xiàn)prim算法的功能。(4)、如何從每個頂點開始找到所有的最小生成樹的頂點。(5)、如何輸出最小生成樹的邊及其權值。此問題的關鍵在于如何實現(xiàn)prim算法，實現(xiàn)的過程中如何得到構成最小生成樹的所有頂點，此外輸出也是一個關鍵問題所在，在此過程中經(jīng)過了多次調試。首先我們對問題進行大致的概要分析：這個問題主要牽涉到通過pri

3、m的基本算法思想實現(xiàn)程序所要求的功能，該算法的主要思想是：假設n=（v，e）是連通網(wǎng)，te是n上最小生成樹中邊的集合。算法從u=u0( u0v),te=開始，重復執(zhí)行下述操作：在所有uu,vv-u的邊（u,v）e中找一條代價最小的邊（u0,v0）并入集合te，同時v0并入u，直至u=v為止。此時te中必有n-1條邊，則t=（v，e）為n的最小生成樹。問題的輸入數(shù)據(jù)的格式為：首先提示輸入帶權網(wǎng)絡的頂點邊數(shù)，我定義的為整形數(shù)據(jù)型，然后輸入每一條邊的信息，即邊的兩個頂點以及權值，是十進制整數(shù)類型，這樣我們就建立一個帶權網(wǎng)絡，并用鄰接矩陣來存儲，生成一個方陣顯示出來。問題的輸出數(shù)據(jù)格式為：輸出是以鄰接

4、矩陣形式輸出，以及從不同頂點開始生成的最小生成樹。題目要求以及達到目標：題目要求用prim算法實現(xiàn)給定無向網(wǎng)中邊e和頂點n實現(xiàn)生成的最小生成樹，輸出生成樹中的各邊及權值。- 18 -三、測試數(shù)據(jù)第一組頂點數(shù)（vertices）、邊數(shù)（edge）：4、5起始節(jié)點（starting）、下個節(jié)點（terminal）、權值（weights）：1,2,11,3,22,4,53,4,41,4,6預測結果1、2、4第二組頂點數(shù)（vertices）、邊數(shù)（edge）：6，10，起始節(jié)點（starting）、下個節(jié)點（terminal）、權值（weights）：1,2,61,3,11,4,52,3,52,5,3

5、3,5,63,4,53,6,44,6,25,6,6預測結果1、4、2、5、3 四、算法思想普里姆算法的基本思想：普里姆算法是另一種構造最小生成樹的算法，它是按逐個將頂點連通的方式來構造最小生成樹的。從連通網(wǎng)絡 n = v, e 中的某一頂點 u0 出發(fā)，選擇與它關聯(lián)的具有最小權值的邊(u0, v)，將其頂點加入到生成樹的頂點集合u中。以后每一步從一個頂點在u中，而另一個頂點不在u中的各條邊中選擇權值最小的邊(u, v),把該邊加入到生成樹的邊集te中，把它的頂點加入到集合u中。如此重復執(zhí)行，直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合u中為止。假設n=(v，e)是一個連通網(wǎng)，te是n上最小生成樹

6、中邊的集合。則構造n的最小生成樹的步驟如下： （1）初始狀態(tài)，te為，u=u0，u0v； （2）在所有uu，vv-u的邊(u，v) e中找一條代價最小的邊(u，v)并入te，同時將v并入u；重復執(zhí)行步驟（2）n-1次，直到u=v為止。在普里姆算法中，為了便于在集合u和(v-u)之間選取權值最小的邊，需要設置兩個輔助數(shù)組closest和lowcost，分別用于存放頂點的序號和邊的權值。 對于每一個頂點vv-u，closestv為u中距離v最近的一個鄰接點，即邊 (v，closestv) 是在所有與頂點v相鄰、且其另一頂點ju的邊中具有最小權值的邊，其最小權值為lowcostv，即lowcostv

7、=costvclosestv，采用鄰接表作為存儲結構：設置一個輔助數(shù)組：lowcost域 存放生成樹頂點集合內頂點到生成樹外各頂點的各邊上的當前最小權值；closest域 記錄生成樹頂點集合外各頂點距離集合內哪個頂點最近(即權值最小)。用prim算法構造最小生成樹的過程：五、模塊劃分（1）預處理#include #include #define inf 9999#define max 40#define linelenght 77（2）建立無向圖int adjg(int gmax) /* 建立無向圖 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(inp

8、ut the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); while(e0.5*n*(n-1)|n=max) /*最大邊數(shù)為，即0.5*n*(n-1)*/ error(); printf(input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; /* 初始化矩陣，全部元素設為無窮大 */ for(k=1;kn|v2n|v11|v21) error()

9、; printf(input the %d on the edge of the starting point, terminal, weights:,k); scanf(%d,%d,%d,&v1,&v2,&weight); gv1v2=weight; /* 無向網(wǎng)的鄰接矩陣是對稱矩陣 */ gv2v1=weight; return(n); /* 返回頂點個數(shù)n */（3）輸出無向圖的鄰接矩陣void pri(int gmax,int n) /* 輸出無向圖的鄰接矩陣 */ int i,j; for(i=0;i=n;i+) printf(%dt,i); for(i=1;i=n;i+) prin

10、tf(n%dt,i); for(j=1;j=n;j+) /* 輸出邊的權值 */ if(gij=inf) printf(%ct,354); else printf(%dt,gij); printf(n);void prim(int gmax,int n) /* prim函數(shù) */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) lowcosti=g1i; /* 初始化 */ closesti=1; lowcost1=0; /* 標志頂點1加入u集合 */ for(i=2;i=n;i+) /* 形成n-1條邊的生成樹 */ mi

11、n=inf; k=0; for(j=2;j=n;j+) /* 尋找權值最小的一條邊，并把權值賦給min */ if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,closestk,k,min); lowcostk=0; /* 頂點k加入u */ for(j=2;j=n;j+) /* 修改由頂點k到其他頂點邊的權值 */ if(gkjlowcostj) lowcostj=gkj; closestj=k; printf(n); （4）輸出一條分割線int priline(int h) /* 輸出一條分割線 */ int

12、 g; printf(n|); for(g=0;gh;g+) printf(*); printf(|n); （5）提示錯誤信息int error() /* 提示錯誤信息 */ printf(nn|*e*r*r*o*r*|n); printf(input errors or data overflow! please re-enternn); fflush(stdin); /* 清除緩存 */ （6）主函數(shù)void main() /* 主函數(shù) */ int gmaxmax,n;priline(linelenght); n=adjg(g);priline(linelenght);priline(l

13、inelenght); printf(input the adjacency matrix without directed graph:n); pri(g,n); printf(n); printf(minimum spanning tree structure:n); prim(g,n); getch();六、算法設計與分析（1）關于帶權網(wǎng)絡的存儲形式 要實現(xiàn)對于任意給定帶權網(wǎng)絡和頂點，運用prim基本算法思想求解所有的最小生成樹的運算。在這里我們首先要明確所選用的數(shù)據(jù)結構，即選用何種數(shù)據(jù)結構存儲來存儲帶權網(wǎng)絡，這是必選首先解決的問題，所以我們選擇了圖的鄰接矩陣存儲方式來存儲帶權網(wǎng)絡，建圖

14、時采用鄰接矩陣的結構，定義鄰接矩陣用到了一維數(shù)組和二維數(shù)組，分別存儲頂點信息和邊的權值。由于該算法對圖中的邊的權值頻繁比較，所以采用鄰接矩陣比較方便，并在此基礎上實現(xiàn)帶權網(wǎng)絡的建立以及輸出顯示。（2）關于普利姆算法的基本思想prim算法求最小生成樹的主要思想此算法是普利姆與1957年提出的一種構造最小生成樹的算法，主要思想是：假設n=（v，e）是連通網(wǎng)，te是n上最小生成樹中邊的集合。算法從u=u0( u0v),te=開始，重復執(zhí)行下述操作：在所有uu,vv-u的邊（u,v）e中找一條代價最小的邊（u0,v0）并入集合te，同時v0并入u，直至u=v為止。此時te中必有n-1條邊，則t=（v，

15、e）為n的最小生成樹。對于最小生成樹問題最小生成樹是指在所有生成樹中，邊上權值之和最小的生成樹，另外最小生成樹也可能是多個，他們之間的權值之和相等。（3）概要設計通過鄰接矩陣的建立，可以將任意兩點的權值存入其中，便于進行各邊的權值的比較修改，在普利姆算法中，為實現(xiàn)這個算法需附設一個輔助數(shù)組closedge，以記錄從u到v-u具有最小代價的邊，對每個頂點viv-u,在輔助數(shù)組中存在一個相應分量closedgei-1，他包括兩個域，其中l(wèi)owcost存儲該邊上的權值。顯然，closedgei-1.lowcost=mincost(u,vi)| uu從算法可以看出每加入一個頂點到u中，closedge

16、數(shù)組都會發(fā)生相應的變化。程序模塊之間的調用：在主函數(shù)中調用鄰接矩陣的初始化函數(shù)，鄰接矩陣的生成函數(shù)，prim算法的函數(shù)，圖的構造函數(shù)，輸出函數(shù)。鄰接矩陣的生成函數(shù)主要解決的是邊的信息存儲問題，而prim算法的函數(shù)是解決計算出最小生成樹的功能。詳細設計和編碼首先我在接下來給出總的流程： main（）調用priline()函數(shù)，即輸出小*調用adjg()函數(shù)，即建立無向圖，后再2次調用priline()函數(shù)調用pri()函數(shù)，即輸出鄰接矩陣最后調用prim（）函數(shù)，即生成最小生成樹結束結果分析：本課程設計的要求對于任意給定的網(wǎng)和起點，用prim算法的基本思想求解出所有的最小生成樹并輸出這些邊的權值

17、，所以如何實現(xiàn)輸出顯示所有的最小生成樹關鍵問題所在，經(jīng)過分析調試，用一個for語句就可以解決這個問題，從每個頂點出發(fā)，開始每一次遍歷并輸出顯示出來。算法的時間和空間性能分析根據(jù)程序中算法的循環(huán)語句可以判斷出普利姆算法的時間復雜度為o（n2）算法和圖中的邊數(shù)無關。因此普利姆算法適合求稠密網(wǎng)的最小生成樹，因為在算法中用鄰接矩陣的存儲結構，在無向圖中，鄰接矩陣是對稱的。所以僅需要存儲上三角或下三角的元素，因此需要n(n+1)的存儲空間。測試結果界面的截圖輸入的情況的截圖輸出結果的截圖輸入錯誤的截圖七、源程序#include #include #define inf 9999#define max 4

18、0#define linelenght 77int adjg(int gmax) /* 建立無向圖 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e); while(e0.5*n*(n-1)|n=max) /*最大邊數(shù)為，即0.5*n*(n-1)*/ error(); printf(input the number of vertices, number of the edge:); scanf(%d,%d,&n,&e

19、); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; /* 初始化矩陣，全部元素設為無窮大 */ for(k=1;kn|v2n|v11|v21) error(); printf(input the %d on the edge of the starting point, terminal, weights:,k); scanf(%d,%d,%d,&v1,&v2,&weight); gv1v2=weight; /* 無向網(wǎng)的鄰接矩陣是對稱矩陣 */ gv2v1=weight; return(n); /* 返回頂點個數(shù)n */void pri(int gmax,

20、int n) /* 輸出無向圖的鄰接矩陣 */ int i,j; for(i=0;i=n;i+) printf(%dt,i); for(i=1;i=n;i+) printf(n%dt,i); for(j=1;j=n;j+) /* 輸出邊的權值 */ if(gij=inf) printf(%ct,354); else printf(%dt,gij); printf(n);void prim(int gmax,int n) /* prim函數(shù) */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) lowcosti=g1i; /*

21、初始化 */ closesti=1; lowcost1=0; /* 標志頂點1加入u集合 */ for(i=2;i=n;i+) /* 形成n-1條邊的生成樹 */ min=inf; k=0; for(j=2;j=n;j+) /* 尋找權值最小的一條邊，并把權值賦給min */ if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,closestk,k,min); lowcostk=0; /* 頂點k加入u */ for(j=2;j=n;j+) /* 修改由頂點k到其他頂點邊的權值 */ if(gkjlowcostj)

22、 lowcostj=gkj; closestj=k; printf(n); int priline(int h) /* 輸出一條分割線 */ int g; printf(n|); for(g=0;gh;g+) printf(*); printf(|n); int error() /* 提示錯誤信息 */ printf(nn|*e*r*r*o*r*|n); printf(input errors or data overflow! please re-enternn); fflush(stdin); /* 清除緩存 */ void main() /* 主函數(shù) */ int gmaxmax,n;p

23、riline(linelenght); n=adjg(g);priline(linelenght);priline(linelenght); printf(input the adjacency matrix without directed graph:n); pri(g,n); printf(n); printf(minimum spanning tree structure:n); prim(g,n); getch();八、測試數(shù)據(jù)第一組第二組九、課程設計項目進度表及任務分配表及任務分配表進度日期 進度2012-1-2搜集資料2012-1-2至3設計算法2012-1-4將問題分塊，然后分塊寫出程序2012-1-5將每塊程序銜接好，進行調試2012-1-5對程序進行最后修改，整理實驗報告分配表成員座號項目內容序號陳娟45號編寫程序 調試程序01謝賢根12號收集資料 調試程序02黃偉偉5號收集資料 調試程序03陳開檳13號 收集資料 word排版04十、設計