PRIM网络的最小生成树普里姆算法

网络的最小生成树普利姆算法

网络的最小生成树普里姆算法

网络的最小生成树普利姆算法

普里姆算法的基本思想如下：假设 G=(V,{E})是连通网，T=(U, {TE})为欲构造的最小生成树。初 始时，U={u0},TE={φ}。重复下 述操作：在所有u∈U,v∈V-U的 边中，选择一条权值最小的边(u, v)并入TE,同时将v并入U,直到 U=V为止。这时产生的TE中具有n1条边。上述过程中求得的T=(U, {TE})便是G的一棵最小生成树。

网络的最小生成树普利姆算法

图1 一个无向图

网络的最小生成树普利姆算法

网络的最小生成树普利姆算法

图2 邻接矩阵

网络的最小生成树普利姆算法

图3 构造最小生成树过程中辅助数组中各分量的值

网络的最小生成树普利姆算法

#include <stdio.h> #include <limits.h> #define INFINITY INT_MAX #define max 40 prim(int g[][max],int n) { int lowcost[max],closest[max]; int i,j,k,min; for(i=2;i<=n;i++) /*n 个顶点*/ { lowcost[i]=g[1][i]; /*初始化*/ closest[i]=1; /*顶点未加入到 最小生成树中*/ }

网络的最小生成树普利姆算法

lowcost[1]=0; /* 标志顶点 1 加入 U 集合 */ for(i=2;i<=n;i++) /* 形成 n-1 条边的生成树*/ { min=INFINITY; k=0; for(j=2;j<=n;j++) /* 寻找 满足边的一个顶点在 U, 另一个顶点在 V 的最小边*/ if((lowcost[j]<min)&&(lowcost[j]!=0)) { min=lowcost[j]; k=j; } printf("(%d,%d)%d\t",closest[k],k,min); lowcost[k]=0; /* 顶点 k 加入 U*/ for(j=2;j<=n;j++) /* 修改由顶点 k 到其他顶点 边的权值*/ if(g[k][j]<lowcost[j]) { lowcost[j]=g[k][j]; closest[j]=k; } printf("\n"); }

网络的最小生成树普利姆算法

int adjg(int g[][max]) /* 建立无向图*/ { int n,e,i,j,k,v1,v2,weight; printf(" 输入顶点个数，边的条数： "); scanf("%d,%d",&n,&e); for(i=1;i<=n;i++) for(j=1;j<=n;j++) g[i][j]=INFINITY; /*初始化矩 阵，全部元素设为无穷大*/ for(k=1;k<=e;k++) { printf(" 输入第 %d 条边的起点，终点，权 值 :",k); scanf("%d,%d,%d",&v1,&v2,&weight); /*输入 一条边的两个顶点序号和权值*/ g[v1][v2]=weight; g[v2][v1]=weight; } return(n); /*返回顶点数*/ }

网络的最小生成树普利姆算法

void prg(int g[][max],int n) /* 输出无 向图的邻接矩阵*/ { int i,j; for(i=0;i<=n;i++) printf("%d\t",i); for(i=1;i<=n;i++) { printf("\n%d\t",i); for(j=1;j<=n;j++) printf((g[i][j]==INFINITY)?"MAX\t":"%d\t",g[ i][j]); } printf("\n"); }

网络的最小生成树普利姆算法

main() { int g[max][max],n; n=adjg(g); /*建立无向图的邻接矩阵 */ printf(" 输出无向图的邻接矩阵 :\n"); prg(g,n); printf(" 最小生成树的构造 :\n"); prim(g,n); }

网络的最小生成树普利姆算法

输入： 输入顶点个数，边的条数：6,10 输入第 1 条边的起点，终点，权值 :1,2,6 输入第 2 条边的起点，终点，权值 :1,3,1 输入第 3 条边的起点，终点，权值 :1,4,6 输入第 4 条边的起点，终点，权值 :2,3,5 输入第 5 条边的起点，终点，权值 :2,5,3 输入第 6 条边的起点，终点，权值 :3,4,5 输入第 7 条边的起点，终

点，权值 :3,5,6 输入第 8 条边的起点，终点，权值 :3,6,4 输入第 9 条边的起点，终点，权值 :4,6,2 输入第 10 条边的起点，终点，权值 :5,6,6

网络的最小生成树普利姆算法

输出无向图的邻接矩阵 :

网络的最小生成树普利姆算法

最小生成树的构造 : (1,3) 1 (3,6) 4 (6,4) 2 (3,2) 5 (2,5) 3