普里姆算法Prim求最小生成樹C程序

1、程序測試用例如下:16 />程序運行過程截圖:源程序清單如下：#include <stdio.h>#define n 6#define MaxNum 10000/*定義一個最大整數(shù)*/*定義鄰接矩陣類型*/typedef int adjmatrixn+1n+1; /*0 號單元沒用 */typedef struct(int fromvex,tovex;int weight;Edge;typedef Edge *EdgeNode;int arcnum;/*邊的個數(shù) */*建立圖的鄰接矩陣*/void CreatMatrix(adjmatrix GA)int i,j,k,e;pr

2、intf("圖中有%d個頂點n",n);for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i=j)GAij=0;/*對角線的值置為0*/elseGAij=MaxNum;/*其它位置的值置初始化為一個最大整數(shù)*/printf("請輸入邊的個數(shù)：");scanf("%d",&arcnum);printf("請輸入邊的信息，按照起點，終點，權(quán)值的形式輸入：n");for(k=1;k<=arcnum;k+)scanf("%d,%d,%d”,&i,&j,

3、&e);/*讀入邊的信息 */GAij=e;GAji=e;/*初始化圖的邊集數(shù)組*/void InitEdge(EdgeNode GE,int m)(int i;for(i=1;i<=m;i+)(GEi.weight=0;/*根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組*/void GetEdgeSet(adjmatrix GA,EdgeNode GE)( int i,j,k=1;for(i=1;i<=n;i+)(for(j=i+1;j<=n;j+)if(GAij!=0&&GAij!=MaxNum)GEk.fromvex=i;GEk.tovex=j;GEk.wei

4、ght=GAij;k+;/*按升序排列圖的邊集數(shù)組 */void SortEdge(EdgeNode GE,int m)int i,j,k;Edge temp;for(i=1;i<m;i+)k=i;for(j=i+1;j<=m;j+)if(GEk.weight>GEj.weight) k=j; if(k!=i)temp=GEi;GEi=GEk;GEk=temp;/*利用普里姆算法從初始點v出發(fā)求鄰接矩陣表示的圖的最小生成樹*/void Prim(adjmatrix GA,EdgeNode T)(int i,j,k,min,u,m,w;Edge temp;/*給T賦初值，對應(yīng)為

5、 v1依次到其余各頂點的邊*/k=1;for(i=1;i<=n;i+)if(i!=1)Tk.fromvex=1;Tk.tovex=i;Tk.weight=GA1i;k+;/*進(jìn)行n-1次循環(huán)，每次求出最小生成樹中的第k條邊*/for(k=1;k<n;k+)min=MaxNum;m=k;for(j=k;j<n;j+)if(Tj.weight<min)min=Tj.weight;m=j;/*把最短邊對調(diào)到k-1下標(biāo)位置*/temp=Tk;Tk=Tm;Tm=temp;/*把新加入最小生成樹T中的頂點序號賦給j*/j=Tk.tovex;/*修改有關(guān)邊，使T中到T外的每一個頂點保

6、持一條到目前為止最短的邊*/for(i=k+1;i<n;i+)(u=Ti.tovex;w=GAju;if(w<Ti.weight)(Ti.weight=w;Ti.fromvex=j;/*輸出邊集數(shù)組的每條邊*/void OutEdge(EdgeNode GE,int e)(int i;printf("按照起點，終點，權(quán)值的形式輸出的最小生成樹為：n”);for(i=1;i<=e;i+)printf("%d,%d,%dn",GEi.fromvex,GEi.tovex,GEi.weight);void main()adjmatrix GA;Edge GEn*(n-1)/2,Tn;CreatMatrix(GA);InitEdge(G