346.txt

绘制表格 Kruskal算法求得的最小生成树

#include   <iostream.h>   
#include   <stdlib.h>   
#include   <iomanip.h>   
// #include  <MSTree.h>   
  const   int   MaxVertexNum=30;   
  const   int   MaxValue=50;   
  typedef   int   VertexType;   
typedef   VertexType   vexlist[MaxVertexNum];   
typedef   int   adjmatrix[MaxVertexNum][MaxVertexNum];   
struct   edge{ 
	
	int   fromvex;   
	int   endvex;   
	int   weight;   
};   
struct   edgenode{   
	int   adjvex;   
	edgenode   *next;   
};   
void   CreateAM(adjmatrix &GA,int   n,int   e)     
{     
	vexlist   GV;   
	int   i,j,k,w;   
	cout<<"输入"<<n<<"个顶点:(之间用空格隔开)"<<endl;   
	for(i=0;i<n;i++)   
		cin>>GV[i];   
	for(i=0;i<n;i++)   
		for(j=0;j<n;j++){   
			if(i==j)   GA[i][j]=0;   
			else   GA[i][j]=MaxValue;   
		}   
		cout<<"输入"<<e<<"条边:(格式:fromvex   endvex   weight)"<<endl;   
		for(k=0;k<e;k++){   
			cout<<"输入第"<<k+1<<"条边:";   
			cin>>i>>j>>w;   
			GA[i][j]=GA[j][i]=w;   
		}   
}   
    
  edge   *CreateES(int   n,int   e)     
  {  
	  
	  int   i,j,k,w;   
	  vexlist   GV;   
	  cout<<"输入"<<n<<"个顶点:(之间用空格隔开)"<<endl;   
	  for(i=0;i<n;i++)   
		  cin>>GV[i];   
	  cout<<"输入"<<e<<"条边:(格式:fromvex   endvex   weight)"<<endl;   
	  edge   *GE=(edge   *)malloc(e*sizeof(edge));     
	  for(k=0;k<e;k++){   
		  cout<<"输入第"<<k+1<<"条边:";   
		  cin>>i>>j>>w;   
		  GE[k].fromvex=i;   
		  GE[k].endvex=j;   
		  GE[k].weight=w;   
	  }   
	  return   GE;   
  }   
  edge   *SortGE(edge   *GE,int   e)     
  {   
	  int   i,j,flag;   
	  edge   temp;   
	  for(i=0;i<e;i++)   
	  {   
		  flag=0;   
		  for(j=e-1;j>=i;j--)   
			  if(GE[j-1].weight>GE[j].weight){   
				  temp=GE[j-1];   
				  GE[j-1]=GE[j];   
				  GE[j]=temp;   
				  flag=1;   
			  }   
			  if(flag==0)   return   GE;     
	  }   
  }   
  
  edge   *Kruskal(edge   *GE,int   n,int   e)   
  {   
	  int   i,j;   
	  adjmatrix   s;   
	  for(i=0;i<n;i++)   
	  {   
		  for(j=0;j<n;j++)   
			  if(i==j)   s[i][j]=1;   
			  else   s[i][j]=0;   
	  }   
	  int   k(1),d(0),m1,m2;   
	  edge   *C=new   edge[n-1];     
	  for(i=0;i<n-1;i++)     
		  C[i].fromvex=C[i].endvex=C[i].weight=0;   
	  while(k<n)   
	  {   
		  for(i=0;i<n;i++)   
		  {   for(j=0;j<n;j++){   
			  if(GE[d].fromvex==j&&s[i][j]==1)   m1=i;   
			  if(GE[d].endvex==j&&s[i][j]==1)   m2=i;   
		  }   
		  }   
		  if(m1!=m2)   
		  {   
			  C[k-1]=GE[d];   
			  k++;   
			  for(j=0;j<n;j++)   
			  {   
				  s[m1][j]=s[m1][j]||s[m2][j];   
				  s[m2][j]=0;   
			  }   
		  }   
		  d++;   
	  }   
	  return   C;   
  }   
  
  edge   *Prim(adjmatrix   GA,int   n)   
  {   
	  int   i,j,k,min,t,m,w;   
	  edge   *CT=new   edge[n-1];   
	  for(i=0;i<n-1;i++)   
	  {   
		  CT[i].fromvex=0;   
		  CT[i].endvex=i+1;   
		  CT[i].weight=GA[0][i+1];   
	  }   
	  for(k=1;k<n;k++)   
	  {   
		  min=MaxValue;   
		  m=k-1;   
		  for(j=k-1;j<n-1;j++)   
			  if(CT[j].weight<min){   
				  min=CT[j].weight;   
				  m=j;   
			  }   
			  edge   temp=CT[k-1];   
			  CT[k-1]=CT[m];   
			  CT[m]=temp;   
			  j=CT[k-1].endvex;   
			  for(i=k;i<n-1;i++)   
			  {   
				  t=CT[i].endvex;   
				  w=GA[j][t];   
				  if(w<CT[i].weight){   
					  CT[i].weight=w;   
					  CT[i].fromvex=j;   
				  }   
			  }   
	  }   
	  return   CT;   
  }   
  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;   
	  }   
  }