graph.h

是一种数据结构的编程代码

#define Max 6000
#include "path.h"
#include "string.h"
#include "iostream.h"
class MGraph{
public:	
	char V[25][10];
	long mEdge[25][25];
    MGraph();
	int SearchVex(char *a);//确定节点位置
	void PrintVex(int a);//由节点位置打印节点
	void ShortestPath(int st,int nd,long &pathlength,Path *p);
};
//************************************************
MGraph::MGraph()
{long mGraph1[25][25]={ 
		{Max,242,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{242,Max,305,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,305,Max,397,704,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,397,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,704,Max,Max,674,Max,Max,Max,137,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
	    {Max,Max,Max,Max,674,Max,651,Max,Max,Max,349,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,651,Max,825,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,825,Max,622,Max,Max,Max,367,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,622,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,137,Max,Max,Max,Max,Max,695,Max,Max,Max,Max,668,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,349,Max,Max,Max,695,Max,534,Max,Max,Max,Max,Max,511,Max,Max,Max,Max,Max,Max,Max},
	 	{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,534,Max,409,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,367,Max,Max,Max,409,Max,675,Max,Max,Max,Max,Max,902,672,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,675,Max,140,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,140,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,668,Max,Max,Max,Max,Max,Max,1145,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,1154,Max,676,Max,Max,Max,Max,Max,216,1892},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,511,Max,Max,Max,Max,Max,676,Max,842,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,842,Max,967,Max,Max,1100,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,902,Max,Max,Max,Max,Max,967,Max,607,Max,639,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,672,Max,Max,Max,Max,Max,Max,607,Max,255,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,255,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,1100,639,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,216,Max,Max,Max,Max,Max,Max,Max,Max},
		{Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,Max,1892,Max,Max,Max,Max,Max,Max,Max,Max}};
		for(int i=0;i<25;i++)
			for(int j=0;j<25;j++)
				mEdge[i][j]=mGraph1[i][j];
	strcpy(V[0],"haerbin");
	strcpy(V[1],"changchun");
	strcpy(V[2],"shenyang");
	strcpy(V[3],"dalian");
	strcpy(V[4],"tianjin");
	strcpy(V[5],"xuzhou");
	strcpy(V[6],"shanghai");
	strcpy(V[7],"nanchang");
	strcpy(V[8],"fuzhou");
	strcpy(V[9],"beijing");
	strcpy(V[10],"zhengzhou");
	strcpy(V[11],"wuhan");
	strcpy(V[12],"zhuzhou");
	strcpy(V[13],"guangzhou");
	strcpy(V[14],"shenzhen");
	strcpy(V[15],"huhehaote");
	strcpy(V[16],"lanzhou");
	strcpy(V[17],"xian");
	strcpy(V[18],"chengdu");
	strcpy(V[19],"guiyang");
	strcpy(V[20],"liuzhou");
	strcpy(V[21],"nanning");
	strcpy(V[22],"kunming");
	strcpy(V[23],"xining");
	strcpy(V[24],"wulumuqi");
}
//*****************************************************
int MGraph::SearchVex(char *a)
{  int b;
   int i=0;
  while(i<25)
  { 
  b=strcmp(a,V[i]);
  if(b==0) return i;
  else i++;
  }
  return 25;
}
//**********************************************************
void MGraph::PrintVex(int a)
{if(a<25&&a>=0)
 cout<<V[a]<<"  ";
else 
cout<<"无此城市"<<endl;
}
//***************************************************
void MGraph::ShortestPath(int st,int nd,long &pathlength,Path *p)
{    bool final[25];
     long dist[25];
	 long min;
	 bool found;
	 int v1=25;
	for(int v=0;v<25;v++)
	{ 
	final[v]=false;
	dist[v]=mEdge[st][v];
	if(dist[v]<Max) {(p+v)->InsertPath(st);(p+v)->InsertPath(v);}
	}
	dist[st]=0;
	final[st]=true;
	found=false;// 完成初始化
	while(!found)
	{ min=Max;
	  for(int w=0;w<25;w++)
         if(!final[w])
			 if(dist[w]<min) {v1=w;min=dist[w];}

		 if(v1==nd) found=true;
		 else 
		 {
			 final[v1]=true;
		     for(int w=0;w<25;w++)
				 if(!final[w]&&(min+mEdge[v1][w]<dist[w]))
				 {
					 dist[w]=min+mEdge[v1][w];
					 (p+w)->CopyPath(p+v1);
					 (p+w)->InsertPath(w);
				 }
		 }
	}
 pathlength=dist[nd];
 

}