图广度2.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 int EdgeType;					//边上的权值类型应由用户定义
typedef struct {
	VertexType vexs[MaxVertexNum];		//顶点表
	EdgeType edges[MaxVertexNum][MaxVertexNum];
										//邻接矩阵，可看作边表
	int n,e;							//图中当前的顶点数和边数
}MGraph;

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 CreateMGraph(MGraph *G);
	void PrintMGraph(MGraph *G);
	void BFSM(MGraph *G,int k);
	MGraph G;
	CreateMGraph(&G);
	PrintMGraph(&G);
	printf("广度优先搜索结果：");
	BFSM(&G,0);
	printf("\n");
}

void CreateMGraph(MGraph *G)
{	//建立无向网的邻接矩阵表示
	int i,j,k,w;
	printf("请输出顶点数和边数：");
	scanf("%d%d",&G->n,&G->e);			//输入顶点数和边数
	printf("请输出顶点信息：");
	for(i=0;i<G->n;i++)					//读入顶点信息，建立顶点表
		while((G->vexs[i]=getchar())=='\n');
	for(i=0;i<G->n;i++)	printf("%c",G->vexs[i]);
	for(i=0;i<G->n;i++)
		for(j=0;j<G->n;j++)
			G->edges[i][j]=0;			//邻接矩阵初始化
	for(k=0;k<G->e;k++) {				//读入e条边，建立邻接矩阵
		printf("\n请输出第%d边的起点、终点和权：",k+1);
		scanf("%d%d%d",&i,&j,&w);		//输入边(vi,vj)上的权w
		G->edges[i][j]=w;
		G->edges[j][i]=w;
	}
}

//打印无向图的邻接矩阵
void PrintMGraph(MGraph *G)
{
	int i,j;
	printf("无向图的邻接矩阵为：\n");
	for(i=0;i<G->n;i++)
	{
		for(j=0;j<G->n;j++)
			printf("%d\t",G->edges[i][j]);
		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 BFSM(MGraph *G,int k)
{	//以vk为源点对用邻接矩阵表示的图G进行广度优先搜索
	int i,j;
	CirQueue Q;

	InitQueue(&Q);
	printf("%c",G->vexs[k]);			//访问源点vk
	visited[k]=TRUE;
	EnQueue(&Q,k);
	while(!QueueEmpty(&Q)) {
		i=DeQueue(&Q);					//vi出队
		for(j=0;j<G->n;j++)				//依次搜索vi的邻接点vj
			if(G->edges[i][j]==1 &&!visited[j])
			{							//vj未访问
				printf("%c",G->vexs[j]);//访问vj
				visited[j]=TRUE;
				EnQueue(&Q,j);			//访问过的vj入队
			}
		}
}