图广度1.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;//将队列中元素的数据类型改为Person

//循环队列的类型定义
#define QueueSize 100	//应根据具体情况定义该值
typedef struct
{	int front;			//头指针，队非空时指向队头元素
	int rear;			//尾指针，队非空时指向队尾元素的下一位置
	int count;			//计数器，记录队中元素总数
	DataType data[QueueSize];
} CirQueue;

#define MaxVertexNum 100			//最大顶点数，应由用户定义
typedef char VertexType;			//顶点类型应由用户定义
typedef struct node {				//边表结点
	int adjvex;						//邻接点域
	struct node *next;				//链域
	//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedef struct vnode {				//顶点表结点
	VertexType vertex;				//顶点域
	EdgeNode *firstedge;			//边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
	//AdjList是邻接表类型
typedef struct {
	AdjList adjlist;				//邻接表
	int n,e;						//图中当前顶点数和边数
}ALGraph;
	//对于简单的应用，无须定义此类型，可直接使用AdjList类型

typedef enum{FALSE,TRUE} Boolean;	//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum];		//访问标志向量是全局量

void main()
{
	void InitQueue(CirQueue *Q);
	int QueueEmpty(CirQueue *Q);
	int QueueFull(CirQueue *Q);
	void EnQueue(CirQueue *Q,DataType x);
	DataType DeQueue(CirQueue *Q);
	DataType QueueFront(CirQueue *Q);
	void CreateALGraph(ALGraph *G);
	void PrintALGraph(ALGraph *G);
	void BFS(ALGraph *G,int k);
	ALGraph G;
	CreateALGraph(&G);
	PrintALGraph(&G);
	printf("广度优先搜索结果：");
	BFS(&G,0);
	printf("\n");
}

void CreateALGraph(ALGraph *G)
{	//建立无向图的邻接表表示
	int i,j,k;
	EdgeNode *s;
	printf("请输出顶点数和边数：");
	scanf("%d%d",&G->n,&G->e);					//读入顶点数和边数
	printf("请输出顶点信息：");
	for(i=0;i<G->n;i++){						//建立顶点表
		while((G->adjlist[i].vertex=getchar())=='\n');	//读入顶点信息
		G->adjlist[i].firstedge=NULL;			//边表置为空表
	}
	for(k=0;k<G->e;k++){						//建立边表
		printf("\n请输出第%d边的起点、终点：",k+1);
		scanf("%d%d",&i,&j);					//读入边(vi,vj)的顶点对序号
		s=(EdgeNode *)malloc(sizeof(EdgeNode));	//生成边表结点
		s->adjvex=j;							//邻接点序号为j
		s->next=G->adjlist[i].firstedge;
		G->adjlist[i].firstedge=s;			//将新结点*s插入顶点vi的边表头部
		s=(EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex=i;							//邻接点序号为i
		s->next=G->adjlist[j].firstedge;
		G->adjlist[j].firstedge=s;			//将新结点*s插入顶点vj的边表头部
	}
}

//打印邻接表：
void PrintALGraph(ALGraph *G)
{
	int i;
	EdgeNode *p;
	for(i=0;i<G->n;i++)
	{
		printf("%d %c:\t",i,G->adjlist[i].vertex);
		p=G->adjlist[i].firstedge;
		while(p)
		{
			printf("%d\t",p->adjvex);
			p=p->next;
		}
		printf("\n");
	}
}

void InitQueue(CirQueue *Q)
{	(*Q).front=(*Q).rear=0;
	(*Q).count=0;					//计数器置0
}

int QueueEmpty(CirQueue *Q)
{
	return (*Q).count==0;			//队列无元素为空
}

int QueueFull(CirQueue *Q)
{
	return (*Q).count==QueueSize;
	//队中元素个数等于QueueSize时队满
}

void EnQueue(CirQueue *Q,DataType x)
{
	if (QueueFull(Q))
	{	printf("Queue overflow");
		exit(0);					//队满上溢
	}
	(*Q).count++;					//队列元素个数加1
	(*Q).data[(*Q).rear]=x;			//新元素插入队尾
	(*Q).rear=((*Q).rear+1)%QueueSize;//循环意义下将尾指针加1
}

DataType DeQueue(CirQueue *Q)
{
	DataType temp;
	if (QueueEmpty(Q))
	{	printf("Queue underflow");
		exit(0);					//队空下溢
	}
	temp=(*Q).data[(*Q).front];
	(*Q).count--;					//队列元素个数减1
	(*Q).front=((*Q).front+1)%QueueSize;//循环意义下的头指针加1
	return temp;
}

DataType QueueFront(CirQueue *Q)
{
	if (QueueEmpty(Q))
	{	printf("Queue is empty");
		exit(0);
	}
	return (*Q).data[(*Q).front];
}

void BFS(ALGraph *G,int k)
{	//以vk为源点对用邻接表表示的图G进行广度优先搜索
	int i;
	CirQueue Q;								//须将队列定义中DataType改为int
	EdgeNode *p;

	InitQueue(&Q);							//队列初始化
	printf("%c",G->adjlist[k].vertex);		//访问源点vk
	visited[k]=TRUE;
	EnQueue(&Q,k);			//vk已访问，将其入队。注意，实际上是将其序号入队
	while(!QueueEmpty(&Q)) {				//队非空则执行
		i=DeQueue(&Q);						//相当于vi出队
		p=G->adjlist[i].firstedge;			//取vi的边表头指针
		while(p) {				//依次搜索vi的邻接点vj（令p->adjvex=j）
			if(! visited[p->adjvex]){		//若vj未访问过
				printf("%c",G->adjlist[p->adjvex].vertex);	//访问vj
				visited[p->adjvex]=TRUE;
				EnQueue(&Q,p->adjvex);		//访问过的vj入队
			}
			p=p->next;						//找vi的下一邻接点
		}
	}
}