graph.c

这是我的老师布置的一道图的应用的题目

 int LocateVex(ALGraph G,VertexType u)//定位数据元素的位置
 { 
	int i;
	for(i=0;i<G.vexnum;++i)
		if(strcmp(u,G.vertices[i].data)==0)//这里要用strcmp()不能用==
			return i;
	return -1;//查找失败
 }

 void CreateGraph(ALGraph *G)//建立无向图
 {
	int i,j,k,w;
	VertexType va,vb;
	ArcNode *p;
	FILE *graph=fopen("tu.xsd","r");//打开tu.xsd文件
	if(!graph)//文件不存在
	{
       printf("\n找不到\"tu.xsd\"文件 请确保该文件在当前目录下!\n\n"
		   "若无此文件请联系徐射雕 或到学校邮箱(http://202.194.48.199)\n"
		   "登入 ：用户名 shediao 密码 19870208 下载\n");
       exit(0);
	}
	fscanf(graph,"%d",&(*G).vexnum);//结点数目
	fscanf(graph,"%d",&(*G).arcnum);//边的数目
	for(i=0;i<(*G).vexnum;++i)//输入各个顶点的值
	{
		fscanf(graph,"%s",(*G).vertices[i].data);
		(*G).vertices[i].firstarc=NULL;
	}
	for(k=0;k<(*G).arcnum;++k)
	{
		fscanf(graph,"%s%s%d",va,vb,&w);
		i=LocateVex(*G,va);
		j=LocateVex(*G,vb);
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=j;
		p->info=w;
		p->nextarc=(*G).vertices[i].firstarc;
		(*G).vertices[i].firstarc=p;

		p=(ArcNode*)malloc(sizeof(ArcNode));//为无向图
		p->adjvex=i;
		p->info=w; 
		p->nextarc=(*G).vertices[j].firstarc; 
		(*G).vertices[j].firstarc=p;
	}
	fclose(graph);
 }
 int visited[MAX_VERTEX_NUM];//标记数组
 void DFS(ALGraph G,int v,void(*visit)(VertexType))//从第v个结点深度优先遍历图
 {
	ArcNode *p;
	visited[v]=1;
	visit(G.vertices[v].data);
	p=G.vertices[v].firstarc;
	while(p)
	{
		if(visited[p->adjvex]==0)
		{
			printf("→ ");
			DFS(G,p->adjvex,visit);
		}
		p=p->nextarc;
	}
 }
 void DFSTraverse(ALGraph G,void(*visit)(VertexType))//深度优先遍历整个图
 {
	 int i;
	 for(i=0;i<G.vexnum;i++)
		 visited[i]=0;
	 printf("\n\n从出发点开始进行深优遍历：\n\n");
	 for(i=0;i<G.vexnum;i++)
		 if(visited[i]==0)
			 DFS(G,i,visit);
	 printf("\n");
 }

 typedef int QElemType;//队列的元素定义为int型
 #include"Queue.h"//队列的存储结构
 #include"Queue.c"//队列的基本操作
 void BFSTraverse(ALGraph G,void(*Visit)(char*))//广度优先遍历整个图
 {
	int v,u;
	ArcNode *p;
	LinkQueue Q;
	for(v=0;v<G.vexnum;++v)
		visited[v]=0;
	InitQueue(&Q);
	printf("\n\n从出发点开始进行广优遍历：\n\n");
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
		{
			visited[v]=1;
			Visit(G.vertices[v].data);
			EnQueue(&Q,v);
			while(!QueueEmpty(Q))
			{
				DeQueue(&Q,&u);
				p=G.vertices[u].firstarc;
				while(p)
				{
					if(!visited[p->adjvex])
					{
						visited[p->adjvex]=1;
						printf("→ ");
						Visit(G.vertices[p->adjvex].data);
						EnQueue(&Q,p->adjvex);
					}
					p=p->nextarc;
				}
			}
		}
	printf("\n\n\n");
 }

 void Display(ALGraph G)//输出图中的各个信息
 {
	int i,j=0;
	ArcNode *p;
	printf("\n张家界风景旅游图的%d个景点分别是：\n",G.vexnum);
	printf("\n*************************************************************\n");
	for(i=0;i<G.vexnum;++i)
	{
		printf(" %2d.%-12s",i+1,G.vertices[i].data);
		if((i+1)%4==0)
			printf("\n");
	}
	printf("\n*************************************************************\n\n");
	printf("旅游图的%d条线路及其权值:\n\n",G.arcnum);
	for(i=0;i<G.vexnum;i++)
	{
		p=G.vertices[i].firstarc;
		while(p)
		{
			if(i<p->adjvex)
			{
				printf("(%2d) %s---%s ",++j,G.vertices[i].data,G.vertices[p->adjvex].data);
				printf(": %d\n",p->info);
			}
			p=p->nextarc;
		}
	}
 }