345.cpp

最小生成树问题 问题描述：若要在ｎ个城市之间架设通讯网络

#include <stdio.h>
#include <malloc.h>
#define no 100
int adjmatrix[no+1][no+1];
int n;
void create_adjmatrix()
/*创建邻接矩阵*/
{
	int i,j,k,w;
	printf("n:");
	scanf("%d",&n);
	/*初始化邻接矩阵*/
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adjmatrix[i][j]=32767;
	do
	{
		printf("i,j,w:");
		scanf("%d,%d,%d",&i,&j,&w);/*w为i,j所邻接的边的权值*/
		if(i>n || j>n) break;/*这是一个死循环，这个if是一个出口，只要输入的结点比n大即会退出*/
		adjmatrix[i][j]=w;
		adjmatrix[j][i]=w;
	}while(1);
}

/*Prim（普里姆）算法 */
void prim(int x)
{
	int i,j,closeest[no+1],mintotree[no+1];/*closeest:与谁最近，mintotree:最小到树距离*/
	int k,min;
	for(i=1;i<=n;i++)/*初始化，X入树*/
	{
		closeest[i]=x;
		mintotree[i]=adjmatrix[x][i];
	}
	mintotree[x]=0;
	for(i=2;i<=n;i++)
	{
		min=32767;/*无穷大*/
		for(j=1;j<=n;j++)/*在mintotree中找非0最小值*/
			if(mintotree[j]!=0 && mintotree[j]<min)
			{
				min=mintotree[j];
				k=j;
			}/*k为第1组中（未进树）距树最近的顶点*/
		mintotree[k]=0;/*k入树*/
		for(j=1;j<=n;j++)/*重新计算第1组（未进树）中的结点到树的距离*/
			if(mintotree[j]!=0 && mintotree[j]>adjmatrix[j][k])
			{
				closeest[j]=k;
				mintotree[j]=adjmatrix[j][k];
			}
	}
		for(i=1;i<=n;i++)/*显示结果*/
			if(i!=closeest[i])
				printf("%d---%d,",i,closeest[i]);
}
main()
{
	create_adjmatrix();
	prim(1);
}