【数据结构C语言】BFS广度遍历（附完整代码）

【数据结构C语言】BFS广度遍历（附完整代码）

目录

• 写在前面
• • 1.原理
  • 2.代码实现

写在前面

深度学会了广度有点类似，不过深度是封装栈 *** 作，广度则是队列，先发，有空更新

1.原理 2.代码实现

#include 
#include 

#define MAXSIZE 100
#define GraphINF 88888

//用于Boolean类型
#define TRUE    1
#define FALSE   0

//用于队空返回值
#define Empty  0
#define FEmpty 1

typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; 	 //边上的权值类型应由用户定义
typedef int Boolean; 	 // Boolean是布尔类型,其值是TRUE或FALSE
typedef int Status;		 //返回状态

//定义邻接矩阵存储结构
typedef struct MGraph{

	int numNodes;					//用于记录顶点个数
	int numEdges;					//用于记录边个数
	VertexType vexs[MAXSIZE];		//用于保存顶点元素
	EdgeType arcs[MAXSIZE][MAXSIZE];//用于保存边元素

}MGraph;


//虚拟队列存储结构
typedef struct{
	int rear;				//队尾指针
	int front;				//队首指针
	VertexType QT[];		//保存VertexType顶点信息数组
}SqQueue;


//-----------------------------------------------------------------
//封装队列 *** 作

//队列初始化
void QueueInit(SqQueue **q)
{
	(*q)=(SqQueue*)malloc(sizeof(SqQueue));
	(*q)->front=0;
	(*q)->rear=0;

}

//队空
Status QueueEmpty(SqQueue *q)
{
	if(q->front==q->rear) 
		return Empty;
	else
		return FEmpty;
}

//出队 并返回出队元素
VertexType DeQueue(SqQueue **q)
{
	VertexType devex;
	devex=(*q)->QT[(*q)->front];
	(*q)->front=((*q)->front+1)%MAXSIZE;
	return devex;
}
//入队
void EnQueue(SqQueue **q,VertexType PVex)
{
	(*q)->QT[(*q)->rear]=PVex;
	(*q)->rear=((*q)->rear+1)%MAXSIZE;
}
//销毁队列
void DestoryQueue(SqQueue **q)
{
	free(*q);
}

//-----------------------------------------------------------------
Boolean visited[MAXSIZE]; 			// 定义全局变量 访问标志的数组


//创建邻接矩阵
//定义arcs 邻接矩阵从下标为1开始存储 方便之后用户输入

void CreateMGraph(MGraph **G)
{
	int i,j,k,w;
	(*G)=(MGraph*)malloc(sizeof(MGraph));

//初始化无向图

	//边数、顶点数
	(*G)->numNodes=6;
	(*G)->numEdges=11;

	//顶点表
	(*G)->vexs[0]='0';(*G)->vexs[1]='1';(*G)->vexs[2]='2';
	(*G)->vexs[3]='3';(*G)->vexs[4]='4';(*G)->vexs[5]='5';

	//图

		//先初始化所有为∞
	for(i=0;i<(*G)->numNodes;i++){
		for(j=0;j<(*G)->numNodes;j++){
				(*G)->arcs[i][j]=GraphINF;
		}
	}
		//再初始化有路径
	(*G)->arcs[0][1]=5;(*G)->arcs[0][3]=7;(*G)->arcs[0][5]=3;
	(*G)->arcs[5][0]=3;(*G)->arcs[1][2]=4;(*G)->arcs[2][0]=8;
	(*G)->arcs[2][5]=9;(*G)->arcs[3][5]=6;(*G)->arcs[3][2]=5;
	(*G)->arcs[4][3]=5;(*G)->arcs[5][4]=1;

}


//返回顶点下标函数
int FindIndex(MGraph *G,VertexType v0)
{
	int index;
	for(index=0;indexnumNodes;index++){
		if(G->vexs[index]==v0){
			return index;
		}
	}

}

//打印邻接矩阵
void PrintfMGraph(MGraph *G)
{
	int i,j,k,cnt,elem;
	printf("n邻接矩阵为：nn");
	for(i=0;inumNodes;i++){
		cnt=1;
			for(j=0;jnumNodes;j++){
				if(G->arcs[i][j]==GraphINF){
					printf("  ∞");
				}
				else printf("  %d ",G->arcs[i][j]);

				if(cnt%(G->numNodes)==0){
					printf("n");
				}
				cnt++;
			}
	}
}

void BFS(MGraph *G,VertexType v0)
{
	int i,indexofv0,tempdevex;
	indexofv0=FindIndex(G,v0);
	//虚拟队列
	SqQueue *q;
	QueueInit(&q);

	//初始化visited数组
	for(i=0;inumNodes;i++){
		visited[i]=FALSE;	//所有顶点为未访问状态
	}

	//1.源点入队 标记 打印
	EnQueue(&q,v0);
	visited[indexofv0]=TRUE;
	printf("%c->",v0);
	//主循环
	while(QueueEmpty(q)){
		//1.队首出队
		tempdevex=DeQueue(&q);
   	    indexofv0=FindIndex(G,tempdevex);
		//2.队首邻接入队 标记 打印
		for(i=0;inumNodes;i++){
			//邻接且未访问 进栈标记打印
			if(G->arcs[indexofv0][i]&&visited[i]==FALSE){
				EnQueue(&q,G->vexs[i]);
				visited[i]=TRUE;
				printf("%c",G->vexs[i]);
				if(inumNodes-1){
        			printf("->");
 				}
			}
		}
		
	}



}

int main()
{
	int j;
	MGraph *G;
	CreateMGraph(&G);
	PrintfMGraph(G);
	printf("nn广度非递归遍历搜索结果如下：");
	BFS(G,'0');
	return 0;
}