app.cpp

该程序实现了 无向图的建立和广度优先搜索及输出

//广度优先搜索

#include <stdio.h>
#include <malloc.h>

#include "queue.h"

////////////////////////////////////////

typedef char VertexType;

typedef struct ArcNode
{
	int adjvex;

	ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{
	VertexType data;
	
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct ALGraph
{
	AdjList vertices;

	int vexnum;
}ALGraph; 

////////////////////////////////////////

//建立无向图
int CreateGraph(ALGraph &); 

//确定邻接点在G.vertices[MAX_VERTEX_NUM]中的序号
int GetAdjvex(ALGraph,VertexType);  

//广度优先搜索
void BFSTraverse(ALGraph);

int FirstAdjvex(ALGraph,int);

int NextAdjvex(ALGraph,int,int);

////////////////////////////////////////

void main()
{
	ALGraph G;

	if(CreateGraph(G))
	{
		BFSTraverse(G);	
	}
	else
		printf("创建图失败!\n");
}

int CreateGraph(ALGraph &G)
{
	int i=-1;

	VertexType data;

	printf("输入所有顶点:\n");

	while((data=getchar())!='\n')  //G.vertices[MAX_VERTEX_NUM]存储顶点
	{	
		i++;

		G.vertices[i].data=data;

		G.vertices[i].firstarc=NULL;	
	}

	G.vexnum=i+1;

	////////////////////////////////////	

	int adjvex;   

	ArcNode *p;
	ArcNode *pEnd;

	for(i=0;i<G.vexnum;i++)   //建立邻接点链表 
	{
		printf("输入顶点%c的所有邻接点:\n",G.vertices[i].data);

		pEnd=NULL;

		while((data=getchar())!='\n')
		{
			adjvex=GetAdjvex(G,data);

			if(adjvex==-1)
				return 0;

			p=(ArcNode *)malloc(sizeof(ArcNode));
			p->adjvex=adjvex;

			if(!G.vertices[i].firstarc)
				G.vertices[i].firstarc=p;
			else
				pEnd->nextarc=p;

			pEnd=p;
		}

		if(pEnd)
			pEnd->nextarc=NULL;
	}

	return 1;	
}//CreateGraph

int GetAdjvex(ALGraph G,VertexType data)
{
	int i;

	for(i=0;i<G.vexnum;i++)
		if(G.vertices[i].data==data)
			return i;

	return -1;
}//GetAdjvex

void BFSTraverse(ALGraph G)
{
	int isVisited[MAX_VERTEX_NUM]={0};  //记录顶点是否被访问过

	Queue Q;
	InitQueue(Q);

	///////////////////////////////////

	int i,j;

	int adjvex;

	printf("BFS序列为:\n");

	for(i=0;i<G.vexnum;i++)  //利用一个数组和一个队列作辅助，进行BFS
		if(isVisited[i]==0)
		{
			printf("%c ",G.vertices[i].data);

			isVisited[i]=1;

			EnQueue(Q,i);

			/////////////////////////////////			

			while(Q.front!=Q.rear)
			{
				DeQueue(Q,adjvex);

				for(j=FirstAdjvex(G,adjvex);j>=0;j=NextAdjvex(G,adjvex,j))
					if(isVisited[j]==0)
					{
						printf("%c ",G.vertices[j].data);					
			
						isVisited[j]=1;

						EnQueue(Q,j);
					}		
			}

		}

	printf("\n");

}//BFSTraverse

int FirstAdjvex(ALGraph G,int adjvex)
{
	ArcNode *p;
	p=G.vertices[adjvex].firstarc;

	if(p)
		return p->adjvex;
	else
		return -1;
}//FirstAdjvex

int NextAdjvex(ALGraph G,int adjvex1,int adjvex2)
{
	ArcNode *p;
	p=G.vertices[adjvex1].firstarc;

	while(p && p->adjvex!=adjvex2)
		p=p->nextarc;

	if(p && p->nextarc)
		return p->nextarc->adjvex;
	else
		return -1;
}//NextAdjvex