graph.cpp

一个能求图中任两顶点之间的最短距离的程序

#include"Graph.h"
#include<iostream.h>
#include<fstream.h>
#include<string.h>
int MaxPath=1000000;
int MaxVex=50;
int InCreaceNum=10;


int Locat(ALGraph &G,VertexType info)
{
	int index=0;
	while((index<G.vexnum)&&(strcmp((G.pVNode+index)->data,info)!=0))
			index++;

	if(index>=G.vexnum)
	{
		
		return -1;
	}
	return index;
}

bool ArcIn(ALGraph &G,VertexType &begin,VertexType &end)
{
	int beginindex=Locat(G,begin);
	int endindex=Locat(G,end);
	ArcNode *parc;
	if((beginindex==-1)||(endindex==-1))
		return false;
	parc=(G.pVNode+beginindex)->firstarc;
	while(parc)
	{
		if(parc->adjvex==endindex)
			return true;
		parc=parc->next;
	}
	return false;
}


void CreateG(ALGraph &G,int kind)//构造图
{	
	int vexnum,arcnum;
	cout<<"输入图的顶点数:";
	cin>>vexnum;
	G.vexnum=vexnum;
	cout<<"输入图的边数:";
	cin>>arcnum;
	G.arcnum=arcnum;
	G.pVNode=new VNode[MaxVex];

	VertexType vex;
	for(int i=0;i<vexnum;i++)
	{
		cout<<"输入第"<<i+1<<"个顶点数据:";
		
		cin>>vex;
		if(Locat(G,vex)!=-1)
		{
			cout<<"该顶点已经存在，请重新输入!"<<endl;
			i--;
			continue;
		}
		else
		{
			strcpy((G.pVNode+i)->data,vex);
			(G.pVNode+i)->firstarc=0;
		}
	}
	cout<<"顶点输入完毕!"<<endl;
	cout<<endl;

	for(int j=1;j<=arcnum;j++)
	{
		if(kind==UDG)
			cout<<"输入第"<<j<<"条边(格式:顶点 顶点 ):";
		else if(kind==DG)
			cout<<"输入第"<<j<<"条弧(格式:弧头 弧尾):";
		else if(kind==UDN)
			cout<<"输入第"<<j<<"条边(格式:顶点 顶点 边信息):";
		else if(kind==DN)
			cout<<"输入第"<<j<<"条弧(格式:弧头 弧尾 弧信息):";

		VertexType begin,end;
		int beginindex=0,endindex=0;
		InfoType *info=new InfoType;

		cin>>begin;
		cin>>end;

		if((kind==UDN)||(kind==DN))//如果是网
			cin>>(*info);
		else 
			(*info)=1;
		
		beginindex=Locat(G,begin);
		endindex=Locat(G,end);
		if(beginindex==-1)
		{
			cout<<"起始节点不存在，请重新输入!"<<endl;
			j--;
			continue;
		}
	
		if(endindex==-1)
		{
			cout<<"结束节点不存在，请重新输入!"<<endl;
			j--;
			continue;
		}
		
		if(ArcIn(G,begin,end))
		{
			cout<<"这条边已经存在，请重新输入!"<<endl;
			j--;
			continue;
		}
		
		ArcNode *p=new ArcNode;
		p->adjvex=endindex;
		p->info=info;

		p->next=(G.pVNode+beginindex)->firstarc;
		(G.pVNode+beginindex)->firstarc=p;

		if((kind==UDG)||(kind==UDN))//如果是无向的
		{
			p=new ArcNode;
			p->adjvex=beginindex;
			p->info=info;

			p->next=(G.pVNode+endindex)->firstarc;
			(G.pVNode+endindex)->firstarc=p;
		}
	}
}



bool CreateGraph(ALGraph &G)//构造图
{
	int kind;

	cout<<"请输入图的类型(1:无向图;2:有向图;3:无向网;4:有向网):";
	cin>>kind;
	while((kind!=1)&&(kind!=2)&&(kind!=3)&&(kind!=4))
	{
		cout<<"输入错误!"<<endl;
		cout<<"请输入图的类型(1:无向图;2:有向图;3:无向网;4:有向网):";
	}
	if(cin.fail())
	{
		cout<<"图构造失败!"<<endl;
		return false;
	}
	G.kind=kind;
	CreateG(G,kind);
	cout<<"图构造好了!"<<endl;
	return true;
}



void BFSTraverse(ALGraph &G,void (*visit)(VNode &vnode))//广度优先遍历
{
	Queue Q;
	InitQueue(Q);
	int *pvisited;
	pvisited=new int[G.vexnum];

	for(int i=0;i<G.vexnum;i++)
	{
		pvisited[i]=0;
	}
	
	for(int v=0;v<G.vexnum;v++)
	{
		if(!pvisited[v])
		{
			visit(G.pVNode[v]);		
			pvisited[v]=1;
			EnQueue(Q,v);
		
			while(!QueueEmpty(Q))
			{
				int cur;
				DeQueue(Q,cur);

				ArcNode *parc;
				parc=(G.pVNode+cur)->firstarc;
				while(parc)
				{
					if(pvisited[parc->adjvex]==0)
					{				
						visit(G.pVNode[parc->adjvex]);
						pvisited[parc->adjvex]=1;
						EnQueue(Q,parc->adjvex);
					}
					parc=parc->next;
				}
			}
		}
	}
	
	DestroyQueue(Q);

}



int *pvisited;
void (*visit)(VNode &vnode);


void DFS(ALGraph &G,int v)
{
	pvisited[v]=1;
	visit(G.pVNode[v]);
	ArcNode *arc;
	arc=((G.pVNode+v)->firstarc);
	while(arc)
	{
		int index=arc->adjvex;
		if(!pvisited[index])
			DFS(G,index);
		arc=arc->next;
	}

}

void DFSTraverse(ALGraph &G,void (*traval)(VNode &vnode))//深度优先遍历
{
	visit=traval;
	pvisited=new int[G.vexnum];
	for(int i=0;i<G.vexnum;i++)
		pvisited[i]=0;
	for(int v=0;v<G.vexnum;v++)
	{
		if(!pvisited[v])
			DFS(G,v);
	}
}

void SaveToFile(ALGraph &G,char filename[50])
{
	int kind=G.kind;
	ofstream outfile;
	int i;
	outfile.open(filename);
	outfile<<kind<<endl;
	outfile<<G.vexnum<<"  "<<G.arcnum<<endl;
	for(i=0;i<G.vexnum;i++)
		outfile<<(G.pVNode+i)->data<<"  ";

	outfile<<endl;

	for(i=0;i<G.vexnum;i++)
	{
		ArcNode *parc;
		parc=(G.pVNode+i)->firstarc;
		while(parc)
		{
			if((G.kind==DN)||(G.kind==DG))
			{
				outfile<<(G.pVNode+i)->data<<"   "<<(G.pVNode+parc->adjvex)->data<<"   ";
				if((kind==DN)||(kind==UDN))
					outfile<<*(parc->info);
				outfile<<endl;
			}
			else
			{	
				if(i<parc->adjvex)
				{
					outfile<<(G.pVNode+i)->data<<"   "<<(G.pVNode+parc->adjvex)->data<<"   ";
					if((kind==DN)||(kind==UDN))
						outfile<<*(parc->info);
					outfile<<endl;
				}
			}
			parc=parc->next;
		}
	}
	outfile.close();
}

void ReadFromFile(ALGraph &G,char filename[50])
{
	ifstream infile;
	infile.open(filename);
	infile>>G.kind;
	infile>>G.vexnum>>G.arcnum;
	G.pVNode=new VNode[MaxVex];
	for(int i=0;i<G.vexnum;i++)
	{
		infile>>(G.pVNode+i)->data;
		(G.pVNode+i)->firstarc=0;
	}
	
	for(i=1;i<=G.arcnum;i++)
	{
		VertexType begin,end;
		int beginindex=0,endindex=0;
		InfoType *info=new InfoType;

		infile>>begin;
		infile>>end;

		if((G.kind==UDN)||(G.kind==DN))
			infile>>(*info);
		else (*info)=1;
		
		beginindex=Locat(G,begin);
		endindex=Locat(G,end);

		ArcNode *p=new ArcNode;
		p->adjvex=endindex;
		p->info=info;

		p->next=(G.pVNode+beginindex)->firstarc;
		(G.pVNode+beginindex)->firstarc=p;

		if((G.kind==UDG)||(G.kind==UDN))//如果是无向的
		{
			p=new ArcNode;
			p->adjvex=beginindex;
			p->info=info;
			p->next=(G.pVNode+endindex)->firstarc;
			(G.pVNode+endindex)->firstarc=p;
		}
	}
}

void ToAdjMatrix(ALGraph &G,VertexType *&a,int **&pmatrix)
{
	a=new VertexType[G.vexnum];
	pmatrix=new int*[G.vexnum];
	for(int i=0;i<G.vexnum;i++)
	{
		strcpy(a[i],(G.pVNode+i)->data);
		pmatrix[i]=new int[G.vexnum];
		for(int j=0;j<G.vexnum;j++)
			pmatrix[i][j]=MaxPath;
		ArcNode *parc=(G.pVNode+i)->firstarc;
		while(parc)
		{
			pmatrix[i][parc->adjvex]=*(parc->info);
			parc=parc->next;
		}
		pmatrix[i][i]=0;
	}
}


void MinPath(ALGraph &G,VertexType v0)
{
	int v0index=Locat(G,v0);
	VertexType *pinfo=0;
	int **pmatrix=0;
	ToAdjMatrix(G,pinfo,pmatrix);
	bool *pfinal=new bool[G.vexnum];
	int i;
	int *pD=new int[G.vexnum];
	int **p;
	p=new int*[G.vexnum];
	int *pnum=new int[G.vexnum];
	for(i=0;i<G.vexnum;i++)
	{
		pfinal[i]=false;
		pD[i]=pmatrix[v0index][i];
		p[i]=new int[G.vexnum];
		for(int j=0;j<G.vexnum;j++)
			p[i][j]=0;
		pnum[i]=0;
	}
	int step;
	for(step=1;step<=G.vexnum-1;step++)
	{
		int minindex=0,curmin=pD[0];
		for(int j=0;j<G.vexnum;j++)
		{
			if(j!=v0index)
			{
				if(pfinal[j]==false)
				{
					minindex=j;
					curmin=pD[j];
					break;
				}
			}
		}
		for(int k=j+1;k<G.vexnum;k++)
		{
			if(k!=v0index)
			{
				if((pfinal[k]==false)&&(pD[k]<curmin))
				{
					curmin=pD[k];
					minindex=k;
				}
			}
		}
		pfinal[minindex]=true;
		for(k=0;k<G.vexnum;k++)
		{
			if((pfinal[k]==false)&& (k!=v0index) && (k!=minindex))
			{
				if(pD[k]>curmin+pmatrix[minindex][k])
				{
					pD[k]=curmin+pmatrix[minindex][k];
					for(int m=0;m<pnum[minindex];m++)
					{
						p[k][m]=p[minindex][m];
					}
					p[k][pnum[minindex]]=minindex;
					pnum[k]=pnum[minindex]+1;
				}
			}
		}
	}
	for(i=0;i<G.vexnum;i++)
	{
		if((i!=v0index)&&(pD[i]<MaxPath))
		{
			cout<<"从"<<v0<<" 到 "<<pinfo[i]<<" 的最短距离为:"<<pD[i]<<endl;
			cout<<v0<<"->";
			for(int k=0;k<=pnum[i]-1;k++)
			{
				cout<<pinfo[p[i][k]]<<"->";
			}
			cout<<pinfo[i]<<endl<<endl;
		}
	}

}