graphicdemo.cpp

C语言实现的图的遍历

#include"head.h"
//--------------------------------------------------------------------------------
int Main_Menu()
{
	while(1)
	{
		int choicem=3;
		printf("\n");
		printf("	★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
		printf("   	★                                                          ★\n");
		printf("   	★                  欢迎进入图的遍历演示系统                ★\n");
		printf("   	★                                                          ★\n");
		printf("   	★      本程序以邻接多重表为存储结构，在连通的无向图上实现  ★\n");
		printf("   	★  了连通无向图的深度优先和广度优先遍历。并以用户指定的结  ★\n");
		printf("   	★  点为起点，分别输出每种遍历下的结点访问序列和相应生成树  ★\n");
		printf("   	★  的边集。                                                ★\n");
		printf("   	★                                                          ★\n");
		printf("   	★    姓 名：关 琦    学 号：02D487    班 级：软双212       ★\n");
		printf("   	★                                                          ★\n");
		printf("	★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
		printf("\n");
		printf("          ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
		printf("          ┃                    1.进入系统                        ┃\n");
		printf("          ┃                    0.退出系统                        ┃\n");
		printf("          ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
		printf("           请选择: ");
		scanf("%d",&choicem);
		fflush(stdin);
		switch(choicem)
		{
		case 1: AML_Menu();break;
		case 0:return choicem;
		default:{
					printf("	   输入有误,请重试。\n\n");
				}
		}//switch
	}//while
}
//--------------------------------------------------------------------------------
void main()
{
	int choice;
	while(1)
	{
		choice=Main_Menu();
		if(choice==0)break;
	}
	Dty_Gam(g);					//销毁图
	printf("\n	   谢谢您的光顾，欢迎下次再来！\n\n");
	system("PAUSE");
}

//销毁图函数-----------------------------------------------------------------
void Dty_Gam(AMGraph &g)
{
	NextEdge *p1,*p2;
	int j;
	for(int i=0; i<g.VexNum;i++)
	{ 
		while(g.Adjmulist[i].Edge)       
		{
			p2=g.Adjmulist[i].Edge;
			if(i==p2->Vertex1)
				j=p2->Vertex2;
			else j=p2->Vertex1;
			p1=g.Adjmulist[j].Edge;
			while(p1!=p2 && p1->Edge2!=p2 && p1->Edge1!=p2)
			{
				if(p1->Vertex2==j)
					p1=p1->Edge2;
				else p1=p1->Edge1;
			}
			if(p2->Vertex1==i)
				g.Adjmulist[i].Edge=p2->Edge1;
			else g.Adjmulist[i].Edge=p2->Edge2;
			
			if(p1==p2)
			{
				if(p2->Vertex1==j)
					g.Adjmulist[j].Edge=p2->Edge1;
				else g.Adjmulist[j].Edge=p2->Edge2;
			}
			else                                
			{                                 
				if(p1->Vertex2 == j)
				{
					if(p2->Vertex2==j)
						p1->Edge2=p2->Edge2;
					else p1->Edge2=p2->Edge1;
				}
				else
				{
					if(p2->Vertex2==j)
						p1->Edge1=p2->Edge2;
					else p1->Edge1=p2->Edge1;
				}
			}
			delete p2;    
		}
	}
}

//邻接表菜单------------------------------------------------------------------
void AML_Menu()
{
	while(1)
	{
		int choice=5;
		printf("			        邻接多重表演示\n");
		printf("          ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
		printf("          ┃                   1.生成邻接多重表                   ┃\n");
		printf("          ┃                   2.深度优先遍历                     ┃\n");
		printf("          ┃                   3.广度优先遍历                     ┃\n");
		printf("          ┃                   4.从北京到广州不经郑州             ┃\n");
		printf("          ┃                   0.退出系统                         ┃\n");
		printf("          ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
		printf("           请选择: ");
		scanf("%d",&choice);
		fflush(stdin);
		if(choice==0) break;
		switch(choice)
		{
		case 1: Init_AMnu();break;
		case 2: DFS_AMnu(g);break;
		case 3: BFS_AMnu(g);break;
		case 4: Path_AMnu(g,0);break;
		default:{
					printf("	   输入错误选项,请重试。\n\n");
				}
		}
	}
}

//初始化菜单-------------------------------------------------------------------
void Init_AMnu()
{
	char file[15];
	FILE *fp;
	if(state)
	{
		printf("	   图已生成，请继续其他操作.\n\n");
		return;
	}
	printf("	   请输入包含生成图信息的文件名(如：123.txt):");
	scanf("%s",file);
	if(strlen(file)==0||strlen(file)>15)
	{
		printf("	   请更改文件名为15位之内。\n\n");
		return;
	}
	if((fp=fopen(file,"r"))==NULL)
	{
		printf("	   数据文件不存在!\n\n");
		return;
	}
	else
	{
		Init_Gam(g);
		Creat_Gam(g,fp);		//调用生成图函数
		state=true;
	}
	fclose(fp);
}

//图初始化函数------------------------------------------------------------------
void Init_Gam(AMGraph &g)
{
	int i;
	//初始化邻接多重表，表示一个空的图。
	g.VexNum=0 ;
	g.EdgeNum=0 ;
	//全局变量初始化
	for(i=0;i<=VertexMax;i++)
		Visited[i]=0;			//初始化访问数组
	for(i=0;i<=60;i++)
		TreeEdge[i]=30;			//初始化边集数组
}

//生成图函数------------------------------------------------------------------
void Creat_Gam(AMGraph &g,FILE *fp)
{
	fscanf(fp,"%d,%d",&g.VexNum,&g.EdgeNum);
	printf("\n	   ------------------<生成连通无向图>------------------\n");
	printf("\n	   [顶点数]  %d, [边数]  %d\n\n",g.VexNum,g.EdgeNum);			//打印顶点数和边数
	printf("	   <顶点信息>\n");
	for(int i=0;i<g.VexNum;i++)
	{
		fscanf(fp,"%d.%s",&g.Adjmulist[i].id,&g.Adjmulist[i].data);
		printf("[%2d] %s\t",g.Adjmulist[i].id,g.Adjmulist[i].data);
		g.Adjmulist[i].Edge=NULL;
	}
	printf("\n\n	   <边信息>\n\n");
	printf("	   <边序>\t\t <两端顶点>\t\t<路程(公里)>\n");
	for(int k=0;k<g.EdgeNum;k++)
	{
		int v1,v2,len;
		fscanf(fp,"%d,%d,%d",&v1,&v2,&len);
		printf("	   [%2d]\t\t	%s , %s\t\t%8d\n",k+1,g.Adjmulist[v1].data,g.Adjmulist[v2].data,len);
		//建立无向连通图
		NextEdge *pointer=new  NextEdge;
		pointer->Vertex1=v1;
		pointer->Vertex2=v2;
		pointer->length=len;
		pointer->Edge1=g.Adjmulist[v1].Edge;
		pointer->Edge2=g.Adjmulist[v2].Edge;
		pointer->Mark=false;
		g.Adjmulist[v1].Edge=pointer;
		g.Adjmulist[v2].Edge=pointer;
	}
	printf("\n\n");
}

//深度遍历菜单------------------------------------------------------------------------------------
void DFS_AMnu(AMGraph g)
{
	int vnum;
	int i=1;
	if(!state)
	{
		printf("\n	   请先进行生成邻接多重表操作!\n\n");
		return;
	}
	while(1)
	{
		printf("\n	   请指定深度优先遍历的起点(编号):");
		scanf("%d",&vnum);
		if(vnum<0||vnum>=g.VexNum)
		{
			printf("	   起点不存在,请重试!\n\n");
			return;
		}
		else break;	
	}
	printf("\n从 [%s] 深度优先遍历顺序如下:\n\n",g.Adjmulist[vnum].data);
	printf("[Begin]==>");
	DFS_Gam(g,vnum,Visited);			//调用深度遍历函数进行遍历
	printf("[End]\n\n");
	printf("生成树的边为:\n");
	printf("<Begin>\n");
	for(int p=0;p<(g.VexNum-1)*2;p=p+2)	//打印边集数组中的边顶点
		printf("<%s,%s>\t",g.Adjmulist[TreeEdge[p]].data,g.Adjmulist[TreeEdge[p+1]].data);
	printf("\n<End>\n\n");
	//全局变量重新初始化
	for(i=0;i<g.VexNum;i++)
		Visited[i]=0;
	for(i=0;i<=60;i++)
		TreeEdge[i]=30;
	index=0;
}

//深度遍历函数------------------------------------------------------------------------
void DFS_Gam(AMGraph g,int vnum,int Visited[])
{
	NextEdge *Pointer;						
	Visited[vnum]=1;						//顶点vnum已查找
	Pointer=g.Adjmulist[vnum].Edge;
	printf("%s==>",g.Adjmulist[vnum].data);
	while(Pointer!=NULL)
	{
		if(Pointer->Vertex1==vnum&&!Visited[Pointer->Vertex2])
		{
			TreeEdge[index++]=Pointer->Vertex1;			//将边的顶点录入边集数组中
			TreeEdge[index++]=Pointer->Vertex2;
			DFS_Gam(g,Pointer->Vertex2,Visited);		//递归，对终点进行深度遍历
		}
		if(Pointer->Vertex2==vnum&&!Visited[Pointer->Vertex1])
		{
			TreeEdge[index++]=Pointer->Vertex2;			//将边的顶点录入边集数组中
			TreeEdge[index++]=Pointer->Vertex1;
			DFS_Gam(g,Pointer->Vertex1,Visited);		//递归，对起点进行深度遍历
		}
		if(Pointer->Vertex1==vnum) Pointer=Pointer->Edge1;
		else Pointer=Pointer->Edge2;
	}
}

//广度遍历菜单-----------------------------------------------------------------------------------------
void BFS_AMnu(AMGraph g)
{
	int vnum;
	int i=1;
	if(!state)
	{
		printf("\n	   请先进行生成邻接多重表操作!\n\n");
		return;
	}
	while(1)
	{
		printf("\n	   请指定广度优先遍历的起点(编号):");
		scanf("%d",&vnum);
		if(vnum<0||vnum>=g.VexNum)
		{
			printf("	   起点不存在,请重试!\n\n");
			return;
		}
		else break;
	}
	printf("\n从 [%s] 广度优先遍历顺序如下:\n\n",g.Adjmulist[vnum].data);
	printf("[Begin]==>");
	BFS_Gam(g,vnum,Visited);					//调用广度遍历函数进行遍历
	printf("[End]\n\n");	
	printf("生成树的边为:\n");
	printf("<Begin>\n");
	for(int p=0;p<(g.VexNum-1)*2;p=p+2)			//将边集数组中的边顶点打印
		printf("<%s,%s>\t",g.Adjmulist[TreeEdge[p]].data,g.Adjmulist[TreeEdge[p+1]].data);
	printf("\n<End>\n\n");
	//全局变量初始化
	for(i=0;i<g.VexNum;i++)
		Visited[i]=0;
	for(i=0;i<=60;i++)
		TreeEdge[i]=30;
	index=0;
}

//广度遍历函数-----------------------------------------------------------------------
void BFS_Gam(AMGraph g,int vnum,int Visited[])
{
	int num;
	NextEdge *Pointer;			
	Visited[vnum]=1;							//已查找
	printf("%s==>",g.Adjmulist[vnum].data);
	Pointer=g.Adjmulist[vnum].Edge;
	if(Pointer->Vertex1==vnum)
		Enqueue(Pointer->Vertex1);
	else Enqueue(Pointer->Vertex2);
	while(Front!=Rear)							//判断队列是否为空
	{
		vnum=Dequeue();
		Pointer=g.Adjmulist[vnum].Edge;
		while(Pointer!=NULL)
		{
			if(Pointer->Vertex1==vnum)
			{
				num=Pointer->Vertex2;
				Pointer=Pointer->Edge1;
			}
			else 
			{
				num=Pointer->Vertex1;
				Pointer=Pointer->Edge2;
			}
			if(!Visited[num])
			{
				Visited[num]=1;
				printf("%s==>",g.Adjmulist[num].data);		//打印顶点信息
				TreeEdge[index++]=vnum;						//将边的顶点录入边集数组
				TreeEdge[index++]=num;
				Enqueue(num);
			}
		}
	}
}
//入队列操作-------------------------------------------------------
int Enqueue(int Vertex)
{
	if(Rear>=QueueMax)
		return -1;
	else
	{
		Rear++;					//队列尾端指针后移
		Queue[Rear]=Vertex;		//将值存入队列中
		return 1;
	}
}

//出对列操作--------------------------------------------------------
int Dequeue()
{
	if(Front==Rear)
		return -1;
	else
	{
		Front++;				//对头指针后移
		return Queue[Front];	//返回对头指针
	}
}

//北京－广州（不经郑州）菜单---------------------------------------
void Path_AMnu(AMGraph g,int v)
{
	if(!state)
	{
		printf("\n	   请先进行生成邻接多重表操作!\n\n");
		return;
	}
	int index=0;
	printf("\n	   从北京到广州中途不过郑州的所有简单路径：\n\n");
	Path_Gam(g,v);						//调用Path_Gan寻找路径函数
	
}
//北京－广州（不经郑州）寻找路径函数---------------------------------------
void Path_Gam(AMGraph g,int v)
{
	NextEdge *pointer=g.Adjmulist[v].Edge;
	if(v==23)return;					//到达郑州，返回
	for(int j=0 ;j<index; j++)			//判断是否是简单路径
		if(TreeEdge[j]==v)break;
	if(j<index)return;						//如果是返回
	TreeEdge[index++]=v;				//将结点录入边集数组
	if(v==5)							//到达广州，打印
	{
		printf("[Begin]==>");
		for(int i=0; i<index;i++)
			printf("%s==>",g.Adjmulist[TreeEdge[i]].data);
		printf("[End]\n\n");
		printf("[总路程] %4d(公里)\n",length);
		printf("\n");
	}	
	while(pointer!=NULL)
	{		
		if(pointer->Mark==false)
		{	
			pointer->Mark=true;					//记录边为访问
			length+=pointer->length;			//累加路程
			if(pointer->Vertex1==v)
				Path_Gam(g,pointer->Vertex2);	//递归调用
			else				
				Path_Gam(g,pointer->Vertex1);
			length-=pointer->length;			//进行回溯
			pointer->Mark=false;
		}
		if(pointer->Vertex1==v)pointer=pointer->Edge1;
		else pointer=pointer->Edge2;	
	}
	index--;
}