graph.h

06年全国研究生数学建模竞赛之邮车调度问题的答案程序。可能根据题目给出的地图

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
typedef char ElemType[5];
#define maxnode 90
#define infinity 1000000000

//弧结点：弧头在顶点数组中的序号，权值，指向下一条弧结点的指针
struct ARcType
{
	int adjvertex;
	int weight;
	ARcType* nextarc;
};

//顶点结点：结点名字，指向第一条弧结点的指针
struct VErtexType
{
	ElemType vertexname;
	ARcType *firstarc;
};

struct CLosedge
{
	int adjvex;
	int lowcost;
};

typedef VErtexType adjlisttype[maxnode];//图的邻接矩阵

typedef int* intp;

class GRaph
{
public:
	int vertexnum,arcnum;
	int fenqu[6];
	int arcs[maxnode][maxnode];//图的邻接矩阵
	float A[maxnode][maxnode];//floyd矩阵
	int path[maxnode][maxnode];//记录floyd矩阵的中间点
    adjlisttype graph;//注意此时graph已经是一个VErtexType类型的，具有maxnode个元素的一维数组了！！！！
	int getdata();//读取数据建立邻接表和邻接矩阵
	int LocateVertex(ElemType str);//查找名为str的顶点在数组graph中的序号，返回。没有返回-1
	int FirstAdjVex(int v);//返回邻接表graph中,序号为v的顶点的第一个邻接点在graph中的序号.没有则返回-1
    int NextAdjVex(int v,int w);//返回邻接表graph中，序号为v的顶点的下一个邻接点（相对序号为w）。若w已经是最后一个，返回-1
	int CreateUDN();//用领接表和邻接矩阵方法建立有权无向图
	void ShowUDN();//显示图的领接表的结构
	void ShowUDNMatrix();//显示图的邻接矩阵
	void MiniSpanTree_PRIM(ElemType str);//从名字为str的顶点出发生成最小树。
	void ShortestPath_DIJ(ElemType str,int P[maxnode][maxnode],int *D,int sign[maxnode][maxnode]);//用DIJ算法求从str出发的单源最短路径
	void ShowDIJ(int v,int p[maxnode][maxnode],int *d,int sign[maxnode][maxnode],int y);//显示DIJ算法结果
    void ShowDIJ(int v,int p[maxnode][maxnode],int *d,int sign[maxnode][maxnode]);
    void Floyd();//求floyd矩阵和路径path矩阵
    void Ppath(int i,int j);//向前递归查找路径上的顶点
	void Showpah(int i,int j);//显示邻接表中顶点为i和j的两个点的最短路径,但使用前必须已经用floyd算法算出floyd矩阵和path数组
	void Showpah();//显示邻接表中所有点的最短路径，使用前必须已经用floyd算法算出floyd矩阵和path数组
    void Showpah1(int i,int j);//显示邻接表中顶点为i和j的两个点的中间最短路径,但使用前必须已经用floyd算法算出floyd矩阵和path数组
	float travel(int v0,int *befsome,int k);//不完整售货员回路,vo是出发点在邻接表序号，bef储存要经过的点的序号，k为第几阶段,即集合S里面有k个元素
};

float min(float *d,int n)//返回数组d的最小值
{
	int i;
	float m;
	m=d[0];
	for(i=1;i<n;i++)
		if(m>d[i])m=d[i];
	return m;
}


int minnum(float *d,int n)//返回数组d的最小值的序号
{
	int i,num;
	float m;
	m=d[0];
	num=0;
	for(i=1;i<n;i++)
		if(m>d[i]){m=d[i];num=i;}
	return num;
}

void exchange(int &a,int &b)
{
	int k;
    k=a;
	a=b;
	b=k;
}


int real0;//原点,即出发点
int m;//要经过的顶点数
int sign[100][100];//记录行第k阶段时，列v0的前一个点在邻接表中的序号
int sign1[60];//

float GRaph::travel(int v0,int *befsome,int k)//vo是出发点在邻接表序号，bef储存要经过的点的序号，k为第几阶段,即集合S里面有k个元素
{//使用前要初始化全局变量p[][],floyd矩阵，和使得v0，bef存储相应的序号，k一开始为要经过的顶点数m。
	if(k==0){return A[real0][v0];}
	int i;
  float dis[50];
  for(i=0;i<k;i++)//用bef里的k个轮流出来作为v0的前置点
  {
	  exchange(befsome[i],befsome[k-1]);
	  dis[i]=travel(befsome[k-1],befsome,k-1)+A[befsome[k-1]][v0];//此时的dis[k-1]为原来的dis[i],k-1阶段时S集合为dis[0]->dis[k-2]
      exchange(befsome[i],befsome[k-1]);//换回来
  }
  sign1[k]=befsome[minnum(dis,k)];//选择的标准不但要是最小，而且现在的v0和S（k-1） 个点的集合等于下一步的S（k）里选最小
  return min(dis,k);
}



int inbef(int n,int *a)
{
	int i;
	for(i=0;i<100;i++)
		if(n==a[i])return i;
	return -1;
}


int GRaph::getdata()
{
	ifstream fin;
	fin.open("data.txt",ios::in);
	if(!fin)
	{
		cout<<"error"<<endl;
		exit(0);
	}
	char str1[350][5],str2[350][5];
	int i,dis[350];
	for(i=0;i<340;i++)
	{
		fin>>str1[i];
		fin>>str2[i];
		fin>>dis[i];
	}
	fenqu[0]=1;
	fenqu[1]=17;
	fenqu[2]=27;
	fenqu[3]=34;
	fenqu[4]=44;
	fenqu[5]=58;
	int k,j,m;
	float weight;
    ElemType str,strt,strh;
    ARcType *p,*q;
	//全市的数据录入
	vertexnum=79;
	arcnum=340;

   //输入各个顶点的名字，为string类型
    strcpy(graph[0].vertexname,"D");
    graph[0].firstarc=NULL;
	for(k=1;k<=73;k++)//输入支局的名字
	{
		m=k;
		str[0]='Z';
		if(m<10){str[1]=k+'0';str[2]='\0';}
		else 
		{
			str[2]=m%10+'0';
			m/=10;
			str[1]=m+'0';
			str[3]='\0';
		}
		strcpy(graph[k].vertexname,str);
	    graph[k].firstarc=NULL;
	}
    for(k=74;k<79;k++)//县局的名字
	{
		str[0]='X';
		str[1]=k-73+'0';
		str[2]='\0';
		strcpy(graph[k].vertexname,str);
	    graph[k].firstarc=NULL;
	}

	//初始化邻接矩阵
	for(i=0;i<vertexnum;i++)
		for(j=0;j<vertexnum;j++)
		{
			if(i==j){A[i][j]=arcs[i][j]=0;path[i][j]=-1;}
			else
			{A[i][j]=arcs[i][j]=infinity;path[i][j]=-1;}
		}
	
	
	for(k=0;k<arcnum;k++)
	{
		//cout<<"输入第"<<k+1<<"条弧的第一个顶点的名字:";
	    strcpy(strt,str1[k]);
		i=LocateVertex(strt);
		while(i==-1)
		{
			cout<<"输入有误，没有这个顶点，请重新输入：";
			cin>>strt;
			i=LocateVertex(strt);
		}

	    //cout<<"输入第"<<k+1<<"条弧的第二个顶点的名字:";
	    strcpy(strh,str2[k]);
	    j=LocateVertex(strh);
		while(j==-1)
		{
			cout<<"输入有误，没有这个顶点，请重新输入：";
			cin>>strh;
			j=LocateVertex(strh);
		}

	    //cout<<"输入第"<<k+1<<"条弧的权值:";
	    weight=dis[k];
		A[i][j]=A[j][i]=arcs[i][j]=arcs[j][i]=weight;

	    q=new ARcType;
	    q->adjvertex=j;
	    q->weight=weight;
	    q->nextarc=graph[i].firstarc;
	    graph[i].firstarc=q;
  
	    p=new ARcType;
	    p->adjvertex=i;
	    p->weight=weight;
	    p->nextarc=graph[j].firstarc;
	    graph[j].firstarc=p;
	}
	return 1;
}

void  GRaph::Floyd()//求floyd矩阵和路径path矩阵
{
	int i,j,k;
	for(k=0;k<vertexnum;k++)
	{
		for(i=0;i<vertexnum;i++)
			for(j=0;j<vertexnum;j++)
				if(A[i][j]>A[i][k]+A[k][j])
				{
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				}
	}
}

void GRaph::Ppath(int i,int j)//向后递归查找路径上的顶点
{
   int k;
   k=path[i][j];
   if(k==-1)return;
   Ppath(i,k);
   cout<<graph[k].vertexname<<"->";
   Ppath(k,j);
}

void GRaph::Showpah(int i,int j)//显示邻接表中顶点为i和j的两个点的中间最短路径,但使用前必须已经用floyd算法算出floyd矩阵和path数组
{
	if(A[i][j]>=infinity){cout<<"两点之间没有路径到达。"<<endl;return;}	
	Ppath(i,j);
}

void GRaph::Showpah1(int i,int j)//显示邻接表中顶点为i和j的两个点的中间最短路径,但使用前必须已经用floyd算法算出floyd矩阵和path数组
{
	if(A[i][j]>=infinity){cout<<"两点之间没有路径到达。"<<endl;return;}
	cout<<graph[i].vertexname<<"->";
	Ppath(i,j);
	cout<<graph[j].vertexname<<endl;
}

void GRaph::Showpah()//显示邻接表中所有点的最短路径，使用前必须已经用floyd算法算出floyd矩阵和path数组
{
	int i,j;
	for(i=0;i<vertexnum;i++)
	{
		for(j=0;j<vertexnum;j++)
			if(A[i][j]==infinity)
			{
				if(i!=j)cout<<graph[i].vertexname<<"没有路径到"<<graph[j].vertexname<<endl;
			}

			else
			{
				cout<<graph[i].vertexname<<"到"<<graph[j].vertexname<<"的最短路径为："<<endl;
				cout<<graph[i].vertexname<<"->";
				Ppath(i,j);
				cout<<graph[j].vertexname<<",距离为："<<A[i][j]<<endl;
			}
	}
}
				


int GRaph::LocateVertex(ElemType str)//查找名为str的顶点在数组graph中的序号，返回。没有返回-1
{
	int k;
	for(k=0;k<vertexnum;k++)
	if(strcmp(graph[k].vertexname,str)==0)return k;
	return -1;
}


int GRaph::CreateUDN()//有权无向图的领接表和邻接矩阵
{
	int k,weight,i,j;
    ElemType strt,strh;
    ARcType *p,*q;
    cout<<"输入顶点的数目:";
    cin>>vertexnum;
    cout<<"输入弧结点的数目:";
    cin>>arcnum; 

   //输入各个顶点的名字，为string类型
	for(k=0;k<vertexnum;k++)
	{
		cout<<"输入第"<<k+1<<"个结点的名字:";
		cin>>graph[k].vertexname;
	    graph[k].firstarc=NULL;
	}

	//初始化邻接矩阵
	for(i=0;i<vertexnum;i++)
		for(j=0;j<vertexnum;j++)
		{
			if(i==j)
			{
				A[i][j]=arcs[i][j]=0;
			    path[i][j]=-1;}
			else
			{
				A[i][j]=arcs[i][j]=infinity;
				path[i][j]=-1;
			}
		}
		
	for(k=0;k<arcnum;k++)
	{
		cout<<"输入第"<<k+1<<"条弧的第一个顶点的名字:";
	    cin>>strt;
		i=LocateVertex(strt);
		while(i==-1)
		{
			cout<<"输入有误，没有这个顶点，请重新输入：";
			cin>>strt;
			i=LocateVertex(strt);
		}

	    cout<<"输入第"<<k+1<<"条弧的第二个顶点的名字:";
	    cin>>strh;
	    j=LocateVertex(strh);
		while(j==-1)
		{
			cout<<"输入有误，没有这个顶点，请重新输入：";
			cin>>strh;
			j=LocateVertex(strh);
		}

	    cout<<"输入第"<<k+1<<"条弧的权值:";
	    cin>>weight;
		A[i][j]=A[j][i]=arcs[i][j]=arcs[j][i]=weight;

	    q=new ARcType;
	    q->adjvertex=j;
	    q->weight=weight;
	    q->nextarc=graph[i].firstarc;
	    graph[i].firstarc=q;

	    p=new ARcType;
	    p->adjvertex=i;
	    p->weight=weight;
	    p->nextarc=graph[j].firstarc;
	    graph[j].firstarc=p;
	}
	return 1;
}



void GRaph::ShowUDN()//显示图的领接表的结构
{
	int k;
	ARcType *p;
	for(k=0;k<vertexnum;k++)
	{
		cout<<k+1<<":"<<graph[k].vertexname;
		for(p=graph[k].firstarc;p;p=p->nextarc)
		cout<<"-->"<<graph[p->adjvertex].vertexname;
		cout<<endl;
	}
}

void GRaph::ShowUDNMatrix()
{
	int i,j;
	for(i=0;i<vertexnum;i++)
	{
		for(j=0;j<vertexnum;j++)
		{
			if(arcs[i][j]==infinity)cout<<setfill(' ')<<setw(12)<<"infinity";
			else cout<<setw(12)<<setfill(' ')<<arcs[i][j];
		}
		cout<<endl;
	}
}


int GRaph::FirstAdjVex(int v)
{
	if(!graph[v].firstarc)return -1;
    return graph[v].firstarc->adjvertex;
}

int GRaph::NextAdjVex(int v,int w)
{
	ARcType *p;
	for(p=graph[v].firstarc;p->adjvertex!=w;p=p->nextarc);
	if(!p->nextarc)return -1;
	return p->nextarc->adjvertex;
}

int visit(ElemType str)
{
	if(cout<<str)return 1;
	else return 0;
}


		
void GRaph::MiniSpanTree_PRIM(ElemType str)//从名字为str的顶点出发生成最小树。
{
	int i,u,k,mark,min,dis,count=0;
	CLosedge close[maxnode];
	ARcType *p;
	u=LocateVertex(str);
	//初始化close数组
	for(k=0;k<vertexnum;k++)
		if(k!=u)
		{
			close[k].adjvex=u;
			for(p=graph[u].firstarc;p;p=p->nextarc)
				if(p->adjvertex==k)
				{
					close[k].lowcost=p->weight;
					break;
				}
			if(!p)close[k].lowcost=infinity;
		}

	close[u].lowcost=0;//序号为u的入U集合

	for(i=1;i<vertexnum;i++)
	{
		//先确定T到U的最小权值那个顶点
        min=infinity;
		for(k=0;k<vertexnum;k++)
			if(close[k].lowcost<min&&close[k].lowcost>0)
			{
				min=close[k].lowcost;
				mark=k;
			}
			if(min!=infinity)
			{
				count+=min;
		        close[mark].lowcost=0;//找到T到U最小权值那个顶点序号为mark
		        cout<<graph[close[mark].adjvex].vertexname<<"--"<<graph[mark].vertexname<<endl;
		//修改T与U顶点集之间的最小值
		for(k=0;k<vertexnum;k++)
			if(close[k].lowcost!=0)
			{
				//找到graph[mark]和graph[k]的距离dis
				for(p=graph[mark].firstarc;p;p=p->nextarc)
					if(p->adjvertex==k)break;
				if(p)dis=p->weight;
				else dis=infinity;
				if(dis<close[k].lowcost){close[k].lowcost=dis;close[k].adjvex=mark;}
			}
			}
			else goto A;
	}
A:cout<<"该树的总权值为:"<<count<<endl;
 return;
}

void GRaph::ShortestPath_DIJ(ElemType str,int p[maxnode][maxnode],int *d,int sign[maxnode][maxnode])
{
	//假设D已经有了生成空间。
	int y,v,k,i,w,min,mark,final[maxnode];
	v=LocateVertex(str);
	//初始化final[]，P[][]，D[]
	for(k=0;k<vertexnum;k++)
	{
		final[k]=0;
		d[k]=arcs[v][k];
		for(i=0;i<vertexnum;i++){p[k][i]=0;sign[k][i]=-1;}
		if(d[k]<infinity){p[k][v]=1;p[k][k]=1;sign[k][0]=v;}
	}
	d[v]=0;final[v]=1;
	sign[v][0]=v;
    
	//找最小点,循环vertexnum-1次
	for(i=1;i<vertexnum;i++)
	{
		min=infinity;
		for(k=0;k<vertexnum;k++)
		if(!final[k]&&d[k]<min)
		{
			mark=k;
			min=d[k];
		}
		if(min!=infinity)
		{
		final[mark]=1;
		for(k=0;sign[mark][k]!=-1;k++);
		sign[mark][k]=mark;
		//修改余下点的资料
		for(k=0;k<vertexnum;k++)
			if(!final[k])
				if(d[k]>min+arcs[mark][k])
				{
					d[k]=min+arcs[mark][k];
					for(w=0;sign[mark][w]!=-1;w++)
					{
					p[k][w]=p[mark][w];
					sign[k][w]=sign[mark][w];
					}
					p[k][k]=1;
				}
		}
		else break;
	}
    y=v-74;
	ShowDIJ(v,p,d,sign,y);
}


void GRaph::ShowDIJ(int v,int p[maxnode][maxnode],int *d,int sign[maxnode][maxnode],int y)
{
	int i,j;
	for(i=fenqu[y];i<fenqu[y+1];i++)
		{
		if(!p[i][i]){cout<<graph[v].vertexname<<"没有路径到"<<graph[i].vertexname<<endl;continue;}
			else
			{
                cout<<graph[v].vertexname;
				if(i==v){cout<<"-->"<<graph[v].vertexname;	cout<<" :权值为"<<d[i]<<endl;continue;}
				for(j=0;;j++)
					if(sign[i][j+1]==-1)break;
					else cout<<"-->"<<graph[sign[i][j+1]].vertexname;
			}
			cout<<" :权值为"<<d[i]<<endl;
		}
}
					

void GRaph::ShowDIJ(int v,int p[maxnode][maxnode],int *d,int sign[maxnode][maxnode])
{
	int i,j;
	for(i=0;i<vertexnum;i++)
		{
		if(!p[i][i]){cout<<graph[v].vertexname<<"没有路径到"<<graph[i].vertexname<<endl;continue;}
			else
			{
                cout<<graph[v].vertexname;
				if(i==v){cout<<"-->"<<graph[v].vertexname;	cout<<" :权值为"<<d[i]<<endl;continue;}
				for(j=0;;j++)
					if(sign[i][j+1]==-1)break;
					else cout<<"-->"<<graph[sign[i][j+1]].vertexname;
			}
			cout<<" :权值为"<<d[i]<<endl;
		}
}