Prim算法构造最小生成树

王朝other·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

对于网络,其生成树中的边也带权,将生成树各边的权值总和称为生成树的权,并将权值最小的生成树称为最小生成树(Minimun Spanning Tree),简称为MST。

Prim算法的基本思想是:

(1) 在图G=(V, E) (V表示顶点 ,E表示边)中,从集合V中任取一个顶点(例如取顶点v0)放入集合 U中,这时 U={v0},集合T(E)为空。

(2) 从v0出发寻找与U中顶点相邻(另一顶点在V中)权值最小的边的另一顶点v1,并使v1加入U。即U={v0,v1 },同时将该边加入集合T(E)中。

(3) 重复(2),直到U = V为止。

这时T(E)中有n-1条边,T = (U, T(E))就是一棵最小生成树。

参考程序:

#include <stdio.h>

#define inf 9999

#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个顶点,n-1条边

{lowcost[i]=g[1][i]; //初始化

closest[i]=1; //顶点未加入到最小生成树中

}

lowcost[1]=0; //标志顶点1加入U集合

for(i=2;i<=n;i++) //形成n-1条边的生成树

{min=inf;

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]=inf; //初始化矩阵,全部元素设为无穷大

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]==inf)?"\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);

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航