b.cpp

是一个通讯录的问题

#include <iostream.h>
#include <stdlib.h>
const int MVNum=100;//最大顶点数
const int MAXINT=32767; //全局整型变量
enum boolean {FALSE,TRUE}; //枚举类型
typedef char Vexlist[MVNum]; //顶点数组，类型为CHAR型
typedef int adjmatrix[MVNum][MVNum];

void CreateVexlist(Vexlist GV,adjmatrix GA,int n,int e)
{   //通过从键盘输入的N个顶点和E条边建立顶点数组和邻接矩阵 
	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]=MAXINT;
		 }
	 
    //建立邻接矩阵	 
	cout<<"输入"<<e<<"条边"<<endl;
	for(k=1;k<=e;i++){
		cin>>i>>"">>j>>"">>w;//输入一条边上的端点I，J及边上的权值W
		GA[i][j]=w;
	}
	cout<<GA[i][j]<<endl;
	cout<<"有向图的存储结构建立完毕!"<<endl;
}

//调用弗洛依德算法，求出每对顶点的最短长度对应保存在二维数组A中
void Floyed(adjmatrix GA,adjmatrix A,int n)
{
	int i,j,k;
   //给二维数组赋初值等于图的邻接矩阵GA
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)//设置路径长度D和路径PATH的初值
        	A[i][j]=GA[i][j];//依次以每个顶点作为中间点，逐步优化数组A，求每对顶点之间的最短路径	
		
    for(k=0;k<n;k++)//做K次迭代把顶点K扩充到当前的最短路径PIJ上
	    for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				{
				if(i==k||j==k||i==j)
					continue;
				if(A[i][k]+A[k][j]<A[i][j])
					A[i][j]=A[i][k]+A[k][j];//修改长度
					
			}
   cout<<A[i][j]<<endl;				
}

//求各顶点的偏心度
void FLOYD_PXD(adjmatrix GA,int n)
{ int i,j,k;
  adjmatrix w;
  for(i=0;i<MVNum;i++){
	  for(j=0;j<MVNum;j++)
		  w[i][j]=GA[i][j];//将邻接矩阵复制到W中 
  }
  for(k=0;k<n;k++)//求每对顶点的最短路径
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if( w[i][j]>w[i][k]+w[k][j])
				w[i][j]=w[i][k]+w[k][j];
  
int  GV=1;int dist=MAXINT;//中心点初值顶点为1，偏心度为机器最大数
  
  for(j=0;j<n;j++)
	   {int s=0;
	    for (i=0;i<n;i++)
			if (w[i][j]>s) s=w[i][j];//每列中最大值为该顶点的偏心度
		if(s<dist){dist=s;GV=j;}//各偏心度最小值为中心点
		}
  cout<<"有向图GV的中心点是顶点"<<GV<<endl;
  cout<<" 偏心度是 "<<dist<<endl;
  
}     

//主函数
void main()
{int e;
cout<<"请输入你需要的边数"<<endl;
cin>>e;
int n;
cout<<"请输入你需要的顶点数"<<endl;
cin>>n;
Vexlist GV;
adjmatrix G,GA,A;

  CreateVexlist(GV,G,n,e);
  Floyed(GA,A,n);
  FLOYD_PXD(G,n);
  cout<<"超市的地址应选为"<<GV<<endl;
}