1、一、問題分析和任務定義在n個城市間建立通信網絡，需架設n-1條線路。求解如何以最低經濟代價建設此通信網，這是一個最小生成樹問題。要求：（1）利用普利姆算法求網的最小生成樹；（2）輸出生成樹中各邊及權值。 二、實現本程序需要解決的問題如下(1)、如何選擇存儲結構去建立一個帶權網絡。(2)、如何在所選存儲結構下輸出這個帶權網絡。(3)、如何實現PRIM算法的功能。(4)、如何從每個頂點開始找到所有的最小生成樹的頂點。(5)、如何輸出最小生成樹的邊及其權值。此問題的關鍵在于如何實現PRIM算法，實現的過程中如何得到構成最小生成樹的所有頂點，此外輸出也是一個關鍵問題所在，在此過程中經過了多次調試。首先

2、我們對問題進行大致的概要分析：這個問題主要牽涉到通過PRIM的基本算法思想實現程序所要求的功能，該算法的主要思想是：假設N=（V，E）是連通網，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復執行下述操作：在所有uU,vV-U的邊（u,v）E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。問題的輸入數據的格式為：首先提示輸入帶權網絡的頂點邊數，我定義的為整形數據型，然后輸入每一條邊的信息，即邊的兩個頂點以及權值，是十進制整數類型，這樣我們就建立一個帶權網絡，并用鄰接矩陣來存儲

3、，生成一個方陣顯示出來。問題的輸出數據格式為：輸出是以鄰接矩陣存儲結構下的方陣，以及從不同頂點開始省城的最小生成樹。題目要求以及達到目標：題目要求用普利姆算法實現任意給定的網和頂點的所有最小生成樹，并且輸出各邊的權值。三、測試數據第一組頂點數（vertices）、邊數（edge）：2、1起始節點（starting）、下個節點（terminal）、權值（weights）：1、2、5，預測結果<1,2>5第二組頂點數（vertices）、邊數（edge）：3、3起始節點（starting）、下個節點（terminal）、權值（weights）：1、2、4 1、3、5 2、3、6預測結果

4、<1,2>4、<1,3>5第三組頂點數（vertices）、邊數（edge）：4、5，起始節點（starting）、下個節點（terminal）、權值（weights）：1、2、3 1、3、4 1、4、6 2、4、7 3、4、5預測結果<1,2>3、<1,3>4、<1,4>6 四、算法思想Prim算法求最小生成樹的主要思想此算法是普利姆與1957年提出的一種構造最小生成樹的算法，主要思想是：假設N=（V，E）是連通網，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復執行下述操作：在所有uU,vV-U的邊（u

5、,v）E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。對于最小生成樹問題最小生成樹是指在所有生成樹中，邊上權值之和最小的生成樹，另外最小生成樹也可能是多個，他們之間的權值之和相等。 五、模塊劃分（1）預處理#include <stdio.h>#include <graphics.h>#define inf 9999#define max 40#define linelenght 77（2）普里姆算法void prim(int gmax,int n) /* prim的函數 */

6、int lowcostmax,closestmax; int i,j,k,min; for(i=2;i<=n;i+) /* n個頂點，n-1條邊 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 頂點未加入到最小生成樹中 */ lowcost1=0; /* 標志頂點1加入U集合 */ for(i=2;i<=n;i+) /* 形成n-1條邊的生成樹 */ min=inf; k=0; for(j=2;j<=n;j+) /* 尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊 */ if(lowcostj<min)&&(lowc

7、ostj!=0) min=lowcostj; k=j; printf("(%d,%d)%dt",closestk,k,min); lowcostk=0; /* 頂點k加入U */ for(j=2;j<=n;j+) /* 修改由頂點k到其他頂點邊的權值 */ if(gkj<lowcostj) lowcostj=gkj; closestj=k; printf("n"); （3）輸出分割線int priline(int h) /* 輸出一條分割線 */ int g; printf("n|"); for(g=0;g<h;g+

8、) printf("*"); printf("|n"); （4）提示錯誤信息int error() /* 提示錯誤信息 */ printf("nn|*E*R*R*O*R*|n"); printf("Input errors or Data overflow! please re-enternn"); fflush(stdin); /* 清除緩存 */ （5）建立無向圖int adjg(int gmax) /* 建立無向圖 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf(&qu

9、ot;Input the number of vertices, number of the edge:"); scanf("%d,%d",&n,&e); while(e<=0|e>=n*(n-1)|n>=max) 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+)

10、gij=inf; /* 初始化矩陣，全部元素設為無窮大 */ for(k=1;k<=e;k+) printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); while(v1=v2|v1>n|v2>n|v1<1|v2<1) error(); printf("Input the %d on the edge of the sta

11、rting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n); /* 返回節點個數n */（6）輸出無向圖的鄰接矩陣void pri(int gmax,int n) /* 輸出無向圖的鄰接矩陣 */ int i,j; for(i=0;i<=n;i+) printf("%dt",i); for(i=1;i<=n;i+) printf("n%dt&

12、quot;,i); for(j=1;j<=n;j+) /* 輸出邊的權值 */ if(gij=inf) printf("%ct",'354'); else printf("%dt",gij); printf("n");（7）主函數模塊void main() /* 主函數 */ int gmaxmax,n;priline(linelenght); n=adjg(g);priline(linelenght);priline(linelenght); printf("Input the adjacency m

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

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

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

16、化。程序模塊之間的調用：在主函數中調用鄰接矩陣的初始化函數，鄰接矩陣的生成函數，PRIM算法的函數，圖的構造函數，輸出函數。鄰接矩陣的生成函數主要解決的是邊的信息存儲問題，而PRIM算法的函數是解決計算出最小生成樹的功能。詳細設計和編碼首先我在接下來給出總的流程：Main（）建立圖并初始化圖中信息調用主函數prim找到頂點I信息，并將其加入到數組closedge中與I相鄰的頂點，將它們與之比較，最小的放入cloedgei.lowcost中將找到的所有定點信息都給K，并輸出closedgek.adjvex,closedgek.lowcost G.vexsk結束Main（）結果分析：本課程設計的要

17、求對于任意給定的網和起點，用PRIM算法的基本思想求解出所有的最小生成樹并輸出這些邊的權值，所以如何實現輸出顯示所有的最小生成樹關鍵問題所在，經過分析調試，用一個for語句就可以解決這個問題，從每個頂點出發，開始每一次遍歷并輸出顯示出來。算法的時間和空間性能分析根據程序中算法的循環語句可以判斷出普利姆算法的時間復雜度為O（n2）算法和圖中的邊數無關。因此普利姆算法適合求稠密網的最小生成樹，因為在算法中用鄰接矩陣的存儲結構，在無向圖中，鄰接矩陣是對稱的。所以僅需要存儲上三角或下三角的元素，因此需要n(n+1)的存儲空間。測試結果界面的截圖輸入的情況的截圖輸出結果的截圖輸入錯誤的截圖七、源程序源程

18、序代碼（有注釋詳解）#include <stdio.h>#include <graphics.h>#define inf 9999#define max 40#define linelenght 77void prim(int gmax,int n) /* prim的函數 */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i<=n;i+) /* n個頂點，n-1條邊 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 頂點未加入到最小生成樹中 */ lowcost1=0; /*

19、 標志頂點1加入U集合 */ for(i=2;i<=n;i+) /* 形成n-1條邊的生成樹 */ min=inf; k=0; for(j=2;j<=n;j+) /* 尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊 */ if(lowcostj<min)&&(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(gkj

20、<lowcostj) lowcostj=gkj; closestj=k; printf("n"); int priline(int h) /* 輸出一條分割線 */ int g; printf("n|"); for(g=0;g<h;g+) printf("*"); printf("|n"); int error() /* 提示錯誤信息 */ printf("nn|*E*R*R*O*R*|n"); printf("Input errors or Data overflow!

21、please re-enternn"); fflush(stdin); /* 清除緩存 */ int 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(e<=0|e>=n*(n-1)|n>=max) error(); printf("Input the n

22、umber 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;k<=e;k+) printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&

23、v1,&v2,&weight); while(v1=v2|v1>n|v2>n|v1<1|v2<1) error(); printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n); /* 返回節點個數n */void pri(int gmax,int

24、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 main() /* 主函數 */ int gmaxmax,n;

25、priline(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();八、測試數據第一組第二組第三組九、課程設計項目進度表及任務分配表及任務分配表進度日期 進度201

26、1-1-15搜集資料2011-1-16至17設計算法2011-1-18 將問題分塊，然后分塊寫出程序2011-1-19將每塊程序銜接好，進行調試2011-1-20對程序進行最后修改，整理實驗報告分配表成員座號項目內容序號蔣家權15號編寫程序 調試程序01陳相財25號編寫程序 調試程序02吳繼偉6號收集資料 調試程序03梁麗春7號 收集資料 調試程序04十、設計心得 我們設計的題目是最小生成樹的構造，在這次實踐中遇到了各種問題，碰到問題有時總是百思不得其解最開始，程序要求輸入數值時，如果任意沒有按照程序給定的類型輸入，程序就會出現死循環，雖然加入了檢測程序段，但是當我們不按個數輸入的時候程序也出現了不穩定，又進入死循環了。我們想了很多辦法，其中之一就是加入break這個函數。不過，并沒有出項我們想要的結果，導致循環檢測輸入的函數while無法繼續執行，中途就中