prim.cpp

prim算法构造最小生成树

#include <iostream>
using namespace std;

//prim算法 
#define maxint 6  //0,1,2,3,4,5六个顶点
#define inf    100

int c[6][6]={//图的相邻矩阵，100表示不相邻:6个点，从0开始
	{100,34,46,100,100,19},
	{34,100,100,100,12,100},
	{46,100,100,17,100,25},
	{100,100,17,100,38,25},
	{100,12,100,38,100,26},
	{19,100,25,25,26,100}
};

int  lowcost[maxint];//存放与已生成树的各顶点距离，起始值为与根的距离
int  closest[maxint];//closest[i]存放此时与i最近的顶点
bool s[maxint];      //s[i]表示点i是否在树中



void Prim(int n){

	s[0]=true;//默认第一个点为根
	int i,b,k;//公用变量

    for(i=0;i<n;i++){//初始化两个数组
		lowcost[i]=c[0][i];
		closest[i]=0;//默认为与根顶点最近,其实不是的
		s[i]=false;
	}

	cout<<"\n c[][]\n";//输出c[][]------------------------------
	for(i=0;i<n;i++){
		for(k=0;k<n;k++)
			cout<<"  "<<c[i][k];
	    cout<<endl;
	}
	cout<<endl;

	cout<<"\n各点初始的与已生树的距离 lowcost[]\n";//输出lowcost[]-------------------
	for(i=0;i<n;i++)
		cout<<"  "<<lowcost[i];
	cout<<endl;

	cout<<"\n各点初始的最近点  closest[]\n";//输出closest[]-------------------
	for(i=0;i<n;i++)
		cout<<"  "<<closest[i];
	cout<<endl;

	
    cout<<"\n\n\n￥￥￥￥￥￥￥￥start for....开始检测、加点￥￥￥￥￥￥￥￥￥\n\n";

	for(b=1;b<n;b++){//开始检测、加点***************************************************

  		int min=inf;//设开始时最近距离为极大值
		int j=1;

		for(k=1;k<n;k++){//找出最近点，位置存入j
			if((lowcost[k]<min)&&(!s[k])){
				j=k;
				min=lowcost[k];
			}
		}

		cout<<"第"<<b<<" 次检测，得到："<<j<<"  加入!!  "<<"closest["<<j<<"]="<<closest[j]<<"   即是因与"<<closest[j]<<"相邻且最近而加入"<<endl;
		s[j]=true;//加入j点

		for(k=1;k<n;k++){//更新加入点后的两个数组
			if((c[j][k]<lowcost[k])&&(!s[k])){//因为插入的是j点，所以用j点相邻的距离数组来比较
				lowcost[k]=c[j][k];
				closest[k]=j;
			}
		}

		for(i=0;i<n;i++){//输出已加入的点
			if(s[i]==true)
				cout<<"-------------  "<<i<<" is in s!!!\n";
		}	

		cout<<"\n lowcost[]\n";//输出lowcost[]-------------------
		for(i=0;i<n;i++)
			cout<<"  "<<lowcost[i];
		cout<<endl;


		cout<<"\n closest[]\n";//输出closest[]-------------------
		for(i=0;i<n;i++)
			cout<<"  "<<closest[i];
	     cout<<endl;
	}
}

void main(){
	Prim(6);
}