prim.cpp

经典最小生成树算法--PRIM算法。。C++完整源码

#include <iostream.h>

#define INF 999999                           //定义无穷大值

void Prim(int n, int **c)
{
	int *lowcost;
	int *closest;
	bool *s;

	lowcost = new int[n];
	closest = new int[n];
	s = new bool[n];

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

	cout<<"最小生成树为:";
	cout<<endl;

	for(i=1;i<n;i++)
	{
		int min = INF;
		int j=1;
		for(int k=2;k<=n;k++)
			if((lowcost[k]<min)&&(!s[k]))
			{
				min=lowcost[k];
				j=k;
			}
		cout<<j<<' '<<closest[j]<<endl;

		s[j]=true;
		for(k=2;k<=n;k++)
			if((c[j][k]<lowcost[k])&&(!s[k]))
			{
				lowcost[k] = c[j][k];
				closest[k] = j;
			}
	}
}

int main()
{
	int vexnum;                   //定义图的顶点数和边数
	int edgenum;
	int ver1,ver2,w;
	int **Matrix;                 //定义邻接矩阵

	cout<<"      -------------------------最小生成树问题---------------------"<<endl;
	cout<<endl;
	cout<<"      程序功能：运用Prim算法找出无向图中的最小生成树。"<<endl;
	cout<<"      输入:无向图的相关信息。"<<endl;
	cout<<"      输出:无向图中最小的生成树的各条边。"<<endl;
	cout<<endl;

	cout<<"请输入图的顶点个数:";
	cin>>vexnum;

	cout<<"请输入图中边的条数:";
	cin>>edgenum;

	Matrix = new int*[vexnum+1];           //为邻接矩阵数组开辟空间
	for(int i=0;i<vexnum+1;i++)
		Matrix[i] = new int[vexnum+1];

	for(i=0;i<vexnum+1;i++)               //邻接矩阵的初始化
		for(int j=0;j<vexnum+1;j++)
			Matrix[i][j]=INF;

	for(i=0;i<vexnum+1;i++)
		Matrix[i][i]=0;
	
	cout<<"请输入具有邻接关系的顶点及其权值:";
	cout<<endl;
	for(int j=0;j<edgenum;j++)
	{
		cin>>ver1>>ver2>>w;
		Matrix[ver1][ver2]=w;
		Matrix[ver2][ver1]=w;
	}

	Prim(vexnum, Matrix);

	return 0;
}