大二算法设计实验源码

#include <iostream.h>
void Prim(int,int**);
void main()
{
	int n;
	int **c;
	cout<<"请输入图的结点数：";
	cin>>n;
	c=new int *[n];
	for(int i=0;i<n;i++)
	{
		c[i]=new int[n];
		for(int j=0;j<n;j++)
			c[i][j]=32767;
	}
	int edge;
	cout<<"请输入图的边数：";
	cin>>edge;
	for(i=0;i<edge;i++)
	{
		int x,y;
		int w;
		cout<<"请输入第 "<<i+1<<" 条边的三个参数：\n";
		cout<<"顶点一：";
		cin>>x;
		cout<<"顶点二：";
		cin>>y;
		cout<<"权值：";
		cin>>w;
		c[x-1][y-1]=c[y-1][x-1]=w;
	}
	cout<<"\n最小生成树如下：\n\n";
	cout<<"顶点 边 顶点\n";
	Prim(n,c);
}

void Prim(int n,int **c)
{
	int *lowcost=new int[n];
	int *closest=new int[n];
	bool *s=new bool[n];

	s[0]=true;
	for(int i=1;i<=n;i++)
	{
		lowcost[i]=c[0][i];
		closest[i]=0;
		s[i]=false;
	}

	for(i=1;i<n;i++)
	{
		int min=32767;
		int j=1;
		for(int k=1;k<n;k++)
			if((lowcost[k]<min) && (!s[k]))
			{
				min=lowcost[k];
				j=k;
			}
		cout<<"  "<<closest[j]+1<<"-------"<<j+1<<endl;
		s[j]=true;
		for(k=1;k<n;k++)
			if((c[j][k]<lowcost[k]) && (!s[k]))
			{
				lowcost[k]=c[j][k];
				closest[k]=j;
			}
	}
}