prim.cpp

用prim算法实验最小生成树 本程序中用到函数adjg( )

#include <iostream> 
using namespace std;

#define inf 9999 

#define max 40 

void 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; 
			} 

		cout<<closest[k]<<' '<<k<<' '<<min<<"\t";
		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; 
		} 

		cout<<endl; 

	} 

} 





int adjg(int g[][max]) //建立无向图 
{
	int n,e,i,j,k,v1,v2,weight; 

	cout<<"输入顶点个数，边的条数："; 

	cin>>n>>e; 
	cout<<endl;

	for(i=1;i<=n;i++) 

		for(j=1;j<=n;j++) 

			g[i][j]=inf; //初始化矩阵，全部元素设为无穷大 

	for(k=1;k<=e;k++) 
	{
		cout<<"输入第 "<<k<<" 条边的起点，终点，权值:"; 

		cin>>v1>>v2>>weight; 

		g[v1][v2]=weight; 

		g[v2][v1]=weight; 
	} 

	return n; 
} 





void prg(int g[][max],int n) //输出无向图的邻接矩阵 
{
	int i,j; 
	cout<<' ';
	for(i=1;i<=n;i++) 

		cout<<i<<"\t"; 

	for(i=1;i<=n;i++) 

	{
		cout<<"\n"<<i; 

		for(j=1;j<=n;j++)
			if(g[i][j] == inf)
				cout<<"\t";
			else
				cout<<g[i][j]<<"\t";

	} 

	cout<<"\n"; 	
} 





void main() 
{
	int g[max][max],n; 

	n=adjg(g); 

	cout<<"输出无向图的邻接矩阵:\n"; 

	prg(g,n); 

	cout<<"最小生成树的构造:\n"; 

	prim(g,n); 

}