最小生成树（普林）.cpp

在学习计算算法分析与设计时编写的几个算法代码

/*/#include"iostream.h"
#define MAX 100
#define inf  10
int closest[MAX]={0};

void prim(int n,int c[][7])
{
	int lowcost[MAX]={0};
	
	bool s[MAX];
	s[1]=true;
	for(int i=2;i<=n;i++)
	{
		lowcost[i]=c[1][i];
		//closest[i]=1;
		s[i]=false;
	}
	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<<' '<<lowcost[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;
				}
	}
	

}
main()
{
	int n=6;
	int c[7][7]={{0},{0,0,6,1,5,MAX,MAX},{0,6,0,5,MAX,3,MAX},{0,1,5,0,5,6,4},{0,5,MAX,5,0,MAX,2},{0,MAX,3,6,MAX,0,6},{0,MAX,MAX,4,2,6,0}};
	prim(n,c);
	
}*/
	







#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include "MSTree.h"
void main()
{
int i;
adjmatrix GA;
edge *CT;
edge *C;
edge *GE;
int e,n,ch;
cout<<"***** WELCOME *****"<<endl;
cout<<" 99(9) 刘文澜制作"<<endl;
cout<<"请输入顶点数n,边数e:(用空格隔开)"<<endl;
cin>>n>>e;
cout<<"你打算采用那种算法?"<<endl;
cout<<"1. Kruskal 算法"<<endl;
cout<<"2. Prim 算法"<<endl;
cout<<"请输入你的选择(1 or 2):";
cin>>ch;
switch(ch){
case 1:
GE=CreateES(n,e);
GE=SortGE(GE,e);
cout<<"经过排序后:"<<endl;
cout<<"----------"; //从这里开始绘制表格;
for(i=0;i<e;i++)
cout<<"----";
cout<<endl;
cout<<"fromvex: |";
for(i=0;i<e;i++)
cout<<setw(3)<<GE[i].fromvex<<'|';
cout<<endl;
cout<<"endvex : |";
for(i=0;i<e;i++)
cout<<setw(3)<<GE[i].endvex<<'|';
cout<<endl;
cout<<"weight : |";
for(i=0;i<e;i++)
cout<<setw(3)<<GE[i].weight<<'|';
cout<<endl;
cout<<"----------"; //到这里绘制表格结束;
for(i=0;i<e;i++)
cout<<"----";
cout<<endl;
C=Kruskal(GE,n,e);
cout<<"Kruskal算法求得的最小生成树为:"<<endl;
for(i=0;i<n-1;i++)
cout<<'<'<<C[i].fromvex<<','<<C[i].endvex<<'>'<<C[i].weight<<' ';
cout<<endl<<"处理结束,再见!"<<endl;
break;

case 2:
CreateAM(GA,n,e);
CT=Prim(GA,n);
cout<<"Prim算法求得的最小生成树为:"<<endl;
for(i=0;i<n-1;i++)
cout<<'<'<<CT[i].fromvex<<','<<CT[i].endvex<<'>'<<CT[i].weight<<' ';
cout<<endl<<"处理结束,再见!"<<endl;
break;
default:cout<<"输入有误!"<<endl;
}
}