普里姆算法(Prim)求最小生成树C程序(共5页).doc
精选优质文档-倾情为你奉上1程序测试用例如下：561425523463465程序运行过程截图：源程序清单如下：#include <stdio.h>#define n 6#define MaxNum 10000 /*定义一个最大整数*/*定义邻接矩阵类型*/typedef int adjmatrixn+1n+1; /*0号单元没用*/typedef structint fromvex,tovex;int weight;Edge;typedef Edge *EdgeNode;int arcnum; /*边的个数*/*建立图的邻接矩阵*/void CreatMatrix(adjmatrix GA)int i,j,k,e;printf("图中有%d个顶点n",n);for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i=j)GAij=0; /*对角线的值置为0*/elseGAij=MaxNum; /*其它位置的值置初始化为一个最大整数*/printf("请输入边的个数：");scanf("%d",&arcnum);printf("请输入边的信息，按照起点，终点，权值的形式输入：n");for(k=1;k<=arcnum;k+)scanf("%d,%d,%d",&i,&j,&e); /*读入边的信息*/GAij=e;GAji=e;/*初始化图的边集数组*/void InitEdge(EdgeNode GE,int m)int i;for(i=1;i<=m;i+)GEi.weight=0;/*根据图的邻接矩阵生成图的边集数组*/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.weight=GAij;k+;/*按升序排列图的边集数组*/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出发求邻接矩阵表示的图的最小生成树*/void Prim(adjmatrix GA,EdgeNode T)int i,j,k,min,u,m,w;Edge temp;/*给T赋初值，对应为v1依次到其余各顶点的边*/k=1;for(i=1;i<=n;i+)if(i!=1)Tk.fromvex=1;Tk.tovex=i;Tk.weight=GA1i;k+;/*进行n-1次循环，每次求出最小生成树中的第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;/*把最短边对调到k-1下标位置*/temp=Tk;Tk=Tm;Tm=temp;/*把新加入最小生成树T中的顶点序号赋给j*/j=Tk.tovex;/*修改有关边，使T中到T外的每一个顶点保持一条到目前为止最短的边*/for(i=k+1;i<n;i+)u=Ti.tovex;w=GAju;if(w<Ti.weight)Ti.weight=w;Ti.fromvex=j;/*输出边集数组的每条边*/void OutEdge(EdgeNode GE,int e)int i;printf("按照起点，终点，权值的形式输出的最小生成树为：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(GE,arcnum);GetEdgeSet(GA,GE);SortEdge(GE,arcnum);Prim(GA,T);printf("n");OutEdge(T,n-1);专心-专注-专业
