《普里姆算法(Prim)求最小生成树C程序.docx》由会员分享，可在线阅读，更多相关《普里姆算法(Prim)求最小生成树C程序.docx（5页珍藏版）》请在三一文库上搜索。
1、程序运行过程截图:程序测试用例如下:源程序清单如下：#include #define n 6#define MaxNum 10000/*定义一个最大整数*/*0 号单元没用 */*定义邻接矩阵类型*/typedef int adjmatrixn+1n+1;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
2、(i=1;i=n;i+)for(j=1;j=n;j+)if(i=j)GAij=0;/*对角线的值置为0*/else*/GAij=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+)G
3、Ei.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;im;i+)k=i;for(j=i+1;jGEj.weight) k=j;i
4、f(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;kn;k+)min=MaxNum;m=k;for(j=k;j
5、n;j+)if(Tj.weightmin)min=Tj.weight;m=j;/* 把最短边对调到k-1 下标位置 */temp=Tk;Tk=Tm;Tm=temp;/* 把新加入最小生成树T 中的顶点序号赋给j*/j=Tk.tovex;*/*修改有关边，使T 中到 T 外的每一个顶点保持一条到目前为止最短的边for(i=k+1;in;i+) u=Ti.tovex; w=GAju;if(wTi.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);