graph.h

传统的Dijkstra 算法无疑是解决一般最短路径问题的最优算法

#include"common.h"
//弧结点：弧头在顶点数组中的序号，权值，指向下一条弧结点的指针
struct ARcType
{
	int adjvertex;
	int time;
	int money;
	ElemType lname;//线路名字 
	ARcType* nextarc;
};

void Showall()//显示所有线路的情况
{
		ifstream fin;
		char ch;
		fin.open("txt.txt",ios::in);
		if(!fin)
		{
			cout<<"打开文件错误。"<<endl;
			exit(1);
		}
		while(fin.get(ch))cout<<ch;
		fin.close();
}

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


//e f要初始化
class GRaph
{   
public:
	VErtexType graph[4100];//注意此时graph已经是一个VErtexType类型的，具有maxnode个元素的一维数组了！！！！
	VErtexType graph1[4100];
	int vertexnum,arcnum;
	int L[550];//记录线路i能经过几次换乘到达终点
	ElemType e[600][100],f[600][100];//e[i][j]为线路i会进入站点j，f[i][j]为线路i会从站点j出来
	int en[600],fn[600];//e[i]有多少个站点
	bool ticket[550];//0为单一票制，1为分段计价
	bool round[550];//是环形路为真,否则为假
	void initiate();//初始化en，fn
	void initiate2();
	ElemType r[6000],y[6000];//从E( I ,U)站点发出 的线路集R ( K) ,进入站点F( J ,V) 的线
    //路集Y( O) ;

    int  getdata();//从文件中读入数据
	int LocateVertex(ElemType str);//查找名为str的顶点在数组graph中的序号，返回。没有返回-1
    int findpathout(ElemType s[100],ElemType a);//求出经过站点a的所有线路名字,复制到s[i]中
    int findpathout(ElemType s[100],ElemType a,ElemType hi);
    int findpathin(ElemType s[100],ElemType a);//求出经过站点a的所有线路名字,复制到s[i]中
    int CreateDN();//创建有向有权图的邻接表
	void Insertarc(int i,int j,ElemType linename,ElemType strh,ElemType strt);//在图中加入一条弧，由序号i的点指向序号j的点
    void  Insertarc(int i,int j,ElemType &linename,ElemType strh,ElemType strt,char ch);
	void ShowUDN();//显示图的领接表的结构
	int directpath(ElemType h[100],ElemType t[100],int counth,int countt);//看是否有直接路线
    int ispath(ElemType vhead,ElemType vtail,ElemType hi);//判断vhead和vtail是不是线路hi上的先后两点
	int oncepath(ElemType h[100],ElemType t[100],int counth,int countt);//看是否有转一次车路线,即看线路i和j有没有公共的站点
    int oncepathtime(ElemType h[100],ElemType t[100],int counth,int countt);//看是否有转一次车路线,输出最小时间
    int oncepathsometime(ElemType h[100],ElemType t[100],int counth,int countt);//看是否有转一次车路线,输出最小时间
    int twiceandthreepath(ElemType h[100],ElemType t[100],int counth0,int countt0,int counth1,int countt1);//看是否有转2次车路线,即看线路i和j有没有公共的站点
    int twiceandthreepathtime(ElemType h[100],ElemType t[100],int counth0,int countt0,int counth1,int countt1);//看转两次车的最快时间
    int twiceandthreepathsometime(ElemType h[100],ElemType t[100],int counth0,int countt0,int counth1,int countt1);//看转两次车的最快几次时间
};

void GRaph::initiate()
{
	int i;
	for(i=0;i<550;i++)
		round[i]=ticket[i]=en[i]=fn[i]=0;//ticket[i]为0（false）既是单票制
	for(i=0;i<4100;i++)
	{
		names(graph[i].vertexname,i);
		graph[i].firstarc=NULL;
        names(graph1[i].vertexname,i);
		graph1[i].firstarc=NULL;
	}
	vertexnum=4000;
	arcnum=0;
}

void GRaph::initiate2()
{
	int i,j;
	for(i=0;i<600;i++)
		for(j=0;j<100;j++)
			ev[i][j]=fv[i][j]=false;
    for(i=0;i<550;i++)
		L[i]=0;
}

void  GRaph::Insertarc(int i,int j,ElemType linename,ElemType strh,ElemType strt)
{//在图中加入一条弧，由序号i的站点指向序号j的站点
	//序号为i的站点名字是strh，序号为j的站点名字是strt
	//有个问题是环行线路linename进入的站点不要包括起点
	    ARcType *q,*p;
		int r;
	    q=new ARcType;
	    q->adjvertex=j;
	    q->time=3;
		strcpy(q->lname,linename);
		q->nextarc=graph[i].firstarc;
	    graph[i].firstarc=q;

	    p=new ARcType;
	    p->adjvertex=i;
	    p->time=3;
        strcpy(p->lname,linename);
		p->nextarc=graph1[j].firstarc;
	    graph1[j].firstarc=p;

		r=change(linename);

		strcpy(e[r][++en[r]],strt);
	    strcpy(f[r][++fn[r]],strh);

}

void  GRaph::Insertarc(int i,int j,ElemType &linename,ElemType strh,ElemType strt,char ch)
{//在图中加入一条弧，由序号i的站点指向序号j的站点
	//序号为i的站点名字是strh，序号为j的站点名字是strt
	//有个问题是环行线路linename进入的站点不要包括起点
         int k;
	    linename[4]=ch;
		linename[5]='\0';
	    ARcType *q,*p;
		int r;
	    q=new ARcType;
	    q->adjvertex=j;
	    q->time=3;
		strcpy(q->lname,linename);
		q->nextarc=graph[i].firstarc;
	    graph[i].firstarc=q;

	    p=new ARcType;
	    p->adjvertex=i;
	    p->time=3;
        strcpy(p->lname,linename);
		p->nextarc=graph1[j].firstarc;
	    graph1[j].firstarc=p;

		r=change(linename);

        for(k=1;k<=en[r];k++)
			if(strcmp(e[r][k],strt)==0)break;
		if(k>en[r])strcpy(e[r][++en[r]],strt);

        for(k=1;k<=fn[r];k++)
			if(strcmp(f[r][k],strh)==0)break;
	    if(k>fn[r])strcpy(f[r][++fn[r]],strh);
}

int GRaph::CreateDN()
{
	int k,i,j;
    ElemType lname,strt,strh;
    cout<<"输入顶点的数目:";
    cin>>vertexnum;
    cout<<"输入弧结点的数目:";
    cin>>arcnum; 

   //自动输入各个顶点的名字
	for(k=1;k<=vertexnum;k++)
	{
       names(graph[k].vertexname,k);
        names(graph1[k].vertexname,k);
	    graph[k].firstarc=NULL;
		graph1[k].firstarc=NULL;
	}
	
	for(k=1;k<=arcnum;k++)
	{
		cout<<"输入第"<<k<<"条弧的第一个顶点的名字:";
	    cin>>strh;
		i=LocateVertex(strh);
		while(i==-1)
		{
			cout<<"输入有误，没有这个顶点，请重新输入：";
			cin>>strh;
			i=LocateVertex(strh);
		}

	    cout<<"输入第"<<k<<"条弧的第二个顶点的名字:";
	    cin>>strt;
	    j=LocateVertex(strt);
		while(j==-1)
		{
			cout<<"输入有误，没有这个顶点，请重新输入：";
			cin>>strt;
			j=LocateVertex(strt);
		}
         cout<<"输入第"<<k<<"条弧的名字:";  
         cin>>lname;
		 while(!checkarcname(lname))
		 {
			 cout<<"输入弧名错误，正确应该是“L+四位数字”,请重新输入:";
			 cin>>lname;
		 }

	    Insertarc(i,j,lname,strh,strt);
	}
	return 1;
}


int GRaph::getdata()
{
	int busline,sta1,sta2,i;
	char tickettype[15];//记录线路收费类型
	char ch,str[8];
	ElemType linename,staname1,staname2;
	ifstream fin;
	fin.open("txt.txt");	
	if(!fin)
	{
		cout<<"open error!."<<endl;
		exit(0);
	}
	while(fin){//分为读到第一行L，即线路名，第二行收费表，以及处理第三第四行的或者上下行，或者环线，或者上下行一样
		if((ch=fin.get())=='E')return 1;
		fin.seekg(-1,ios::cur);
		if((ch=fin.get())=='L')
		{//先分析读到线路名
			linename[0]='L';
			i=1;
			while(fin.get(ch)){if(ch!='\n')linename[i++]=ch;else break;}//记录线路名到linename
			linename[i]='\0';
          }
            busline=change(linename);		     
			 i=0;
			 while(fin.get(ch)){if(ch!='\n')tickettype[i++]=ch;else { tickettype[i]='\0';break;}}
			
			if(strcmp(tickettype,"分段计价")==0)//看是分段计价还是单一票制，分段为true
				ticket[busline]=true;//busline为分段计价
			//接下来看是上下行不一样，或者环线，或者上下行一样
			ch=fin.get();
			if(ch=='S')//是上下行一样
			{
				fin>>sta1;//读入第一站号码,sta1为起点号，sta2为终点号
				ch=fin.get();//读'-'
				while(1)
				{             				
				ch=fin.get();//读'S'
				if(ch=='S')fin>>sta2;//建立弧sta1->sta2和sta2->sta1,因为上下行一样
                 names(staname1,sta1);
				 names(staname2,sta2);
                Insertarc(sta1,sta2,linename,staname1,staname2,'U');//上行
                Insertarc(sta2,sta1,linename,staname2,staname1,'D');//下行
				sta1=sta2;
                ch=fin.get();//看读到是否是'-'
				if(ch!='-')break;
				}
				//break跳出循环，证明此时指针已经指向空行，再读一个'\n'使指针指向新的线路
                ch=fin.get();
			}

			else //看是上下行不一样，还是环形
			{
				fin.seekg(-1,ios::cur);//因为上面的if((ch=fin.get())=='S')使得指针往后移动了一字节，现在移回来。因为汉字必须连续两个字节。
                i=0; 
				while(fin.get(ch)){if(ch!='S')str[i++]=ch;else { str[i]='\0';break;}}
				if(strcmp(str,"上行：")==0)//上下行不一样的情形
				{
				    if(ch=='S')
					{
						fin>>sta1;//读入第一站号码,sta1为起点号，sta2为终点号
				        ch=fin.get();//读'-'
				        while(1)
						{             				
					        ch=fin.get();//读'S'
				            if(ch=='S')fin>>sta2;
                            names(staname1,sta1);
						    names(staname2,sta2);
							Insertarc(sta1,sta2,linename,staname1,staname2,'U'); //建立弧sta1->sta2  
				            sta1=sta2;
                            ch=fin.get();//看读到是否是'-'
				            if(ch=='\n')break;
						}//while(1)
					}//if(ch=='S')
				//跳出，证明准备读到"下行:"了
				i=0; 
				while(fin.get(ch)){if(ch!='S')str[i++]=ch;else { str[i]='\0';break;}}
				if(strcmp(str,"下行：")==0)
				{
				    if(ch=='S')
					{
						fin>>sta1;//读入第一站号码,sta1为起点号，sta2为终点号
				        ch=fin.get();//读'-'
				        while(1)
						{             				
							ch=fin.get();//读'S'
				            if(ch=='S')fin>>sta2;//建立弧sta1->sta2
                            names(staname1,sta1);
						    names(staname2,sta2);
							Insertarc(sta1,sta2,linename,staname1,staname2,'D'); 
							sta1=sta2;
                            ch=fin.get();//看读到是否是'-'
				            if(ch=='\n')break;
						}//while(1)
					}//if(ch=='S')
				//跳出，证明准备读到下一条线路了
				}//if(strcmp(str,"下行：")==0)
				}//if(strcmp(str,"上行：")==0)

				if(strcmp(str,"环行：")==0)//环行
				{
					round[busline]=true;
						fin>>sta1;//读入第一站号码,sta1为起点号，sta2为终点号
				        ch=fin.get();//读'-'
				        while(1)
						{             				
							ch=fin.get();//读'S'
				            if(ch=='S')fin>>sta2;//建立弧sta1->sta2
                            names(staname1,sta1);
						    names(staname2,sta2);
							Insertarc(sta1,sta2,linename,staname1,staname2); 
				            sta1=sta2;
                            ch=fin.get();//看读到是否是'-'
				            if(ch!='-')break;
						}
				//break跳出循环，证明此时指针已经指向空行，再读一个'\n'使指针指向新的线路
                ch=fin.get();
				}//if(strcmp(str,"环行：")==0)//环行
			}//else
	}//while(fin)
	fin.close();
	return 0;
}


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

int GRaph::ispath(ElemType vhead,ElemType vtail,ElemType hi)//判断vhead和vtail是不是线路hi上的先后两点
{
	int s,k,n,linenum;
	ARcType *p;
	linenum=change(hi);
	if(round[linenum])return 1;
    s=LocateVertex(vhead);
	n=LocateVertex(vtail);
	k=s;
	if(k==n)return 0;
	while(k!=n)
	{
		for(p=graph[k].firstarc;p;p=p->nextarc)
			if(strcmp(p->lname,hi)==0)
			{
				k=p->adjvertex;	
				if(k==s)return 0;
				break;
			}
	
		if(!p)return 0;
	}
	if(k==n)return 1;
	return 0;
}


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

//第一步，求从站点a开出的所有线路名字,复制到s[i]中
int GRaph::findpathout(ElemType s[100],ElemType a)