广度优先搜索遍历类似于树的层次遍历，按层输出，意味着可以比深度优先搜索遍历少输入边数

1 广度优先搜索遍历连通图无向图

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
//下面三个结构体就是邻接表的结构体，完全一样的方式
typedef struct EdgeNode
{
	int adjvex;
	struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{
	char data;
	EdgeNode* firstedge;
}VertexNode;
typedef struct
{
	VertexNode adjlist[MAXVEX];
	int numVertexs;
	int numEdges;
}GraphAdjlist;
//这里新增队列的代码
typedef struct QueueNode
{
	int data;
	struct QueueNode* next;
}QueueNode;
typedef struct
{
	QueueNode* front;//队头
	QueueNode* rear;//队尾
}Queue;
//初始化
void InitQueue(Queue* Q)
{
	Q->front = Q->rear = NULL;
}
//判空处理
int QueueEmpyt(Queue* Q)
{
	return Q->front == NULL;
}
//入队操作
void enQueue(Queue* Q,int e)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = e;
	newnode->next = NULL;
	if (Q->rear == NULL)
	{
		Q->front = Q->rear = newnode;
	}
	else
	{
		Q->rear->next = newnode;
		Q->rear = newnode;
	}
}
//出队
int deQueue(Queue* Q)
{
	if (QueueEmpyt(Q))
	{
		printf("队空，无输出内容\n");
		exit(1);
	}
	QueueNode* temp = Q->front;
	int data = temp->data;//data保存temp的data，等下返回用，成为我们的新顶点去广度遍历它的邻接j
	Q->front = Q->front->next;
	if (Q->front == NULL)
	{
		Q->rear = NULL;//如果是最后一个数据，那么front和rear同时置为NULL
	}
	free(temp);
	return data;
}
int visited[MAXVEX];//一个标记数组，记录遍历过的不会重复遍历
//创建邻接表
void CreateALGraph(GraphAdjlist* G)
{
	int i, j, k;
	EdgeNode* p;
	printf("请输入顶点数+边数\n");
	scanf("%d%d", &G->numVertexs, &G->numEdges);
	getchar();//接收scanf残留的换行符\n
	printf("请输入顶点的信息\n");
	for (i = 0; i < G->numVertexs; i++)
	{
		scanf("%c", &G->adjlist[i].data);
		G->adjlist[i].firstedge = NULL;//初始化指向边表的指针为null
	}
	for (k = 0; k < G->numEdges; k++)
	{
		printf("请输入(vi,vj)的头，尾,一共有%d条\n", G->numEdges);
		scanf("%d%d", &i, &j);
		//我们这里是实现深度遍历连通图的无向图
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = j;
		p->next = G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = p;

		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = i;
		p->next = G->adjlist[j].firstedge;
		G->adjlist[j].firstedge = p;
	}
	printf("邻接表创建成功\n");
}
void BFS_AL(GraphAdjlist* G, int v)
{
	Queue Q;
	InitQueue(&Q);//初始化队列
	visited[v] = 1;
	enQueue(&Q, v);//入队
	EdgeNode* p;
	while (!QueueEmpyt(&Q))
	{
		int currentVertex = deQueue(&Q);//出队data赋给 currentVertex
		printf("%c ", G->adjlist[currentVertex].data);
		p = G->adjlist[currentVertex].firstedge;
		while (p!=NULL)
		{
			if (visited[p->adjvex] == 0)
			{
				visited[p->adjvex] = 1;
				enQueue(&Q, p->adjvex);
			}
			p = p->next;
		}
	}
}
void BFS(GraphAdjlist* G)
{
	int i;
	for (i = 0; i < G->numVertexs; i++)
	{
		visited[i] = 0;
	}
	for (i = 0; i < G->numVertexs; i++)
	{
		if (visited[i] == 0)
		{
			BFS_AL(G, i);
		}
	}
}
int main()
{
	GraphAdjlist G;
	CreateALGraph(&G);
	printf("广度优先搜索遍历如下\n");
	BFS(&G);
	return 0;
}

  终端连通图输入内容如下:(无向图)

请输入顶点数+边数
8 7
请输入顶点的信息
01234567
请输入(vi,vj)的头，尾,一共有7条
0 1
请输入(vi,vj)的头，尾,一共有7条
0 2
请输入(vi,vj)的头，尾,一共有7条
1 3
请输入(vi,vj)的头，尾,一共有7条
1 4
请输入(vi,vj)的头，尾,一共有7条
3 7
请输入(vi,vj)的头，尾,一共有7条
2 5
请输入(vi,vj)的头，尾,一共有7条
2 6
邻接表创建成功
广度优先搜索遍历如下
0 2 1 6 5 4 3 7

连通图如图：

BFS函数就是也兼容非连通图的了，可以放心使用visited[i]会遍历所有顶点的索引，把非连通图的顶点也会一同遍历，发现为0的就会进入BFS_AL函数进行操作

2 广度优先搜索遍历非连通图无向图

 终端非连通图输入如下:(无向图)

请输入顶点数+边数
8 6
请输入顶点的信息
01234567
请输入(vi,vj)的头，尾,一共有6条
0 1
请输入(vi,vj)的头，尾,一共有6条
1 3
请输入(vi,vj)的头，尾,一共有6条
1 4
请输入(vi,vj)的头，尾,一共有6条
3 7
请输入(vi,vj)的头，尾,一共有6条
2 5
请输入(vi,vj)的头，尾,一共有6条
2 6
邻接表创建成功
广度优先搜索遍历如下
0 1 4 3 7 2 6 5

3 广度优先搜索遍历连通图有向图

请输入顶点数+边数
4 3
请输入顶点的信息
0123
请输入(vi,vj)的头，尾,一共有3条
0 1
请输入(vi,vj)的头，尾,一共有3条
0 2
请输入(vi,vj)的头，尾,一共有3条
2 3
邻接表创建成功
广度优先搜索遍历如下
0 2 1 3