#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100//最大顶点数
typedef struct
{
	int vexs[MAXVEX];//存储顶点的数组
	int matrix[MAXVEX][MAXVEX];//存储邻接矩阵的二维数组
	int vexnum, edgenum;//顶点数+边数
}MGraph;
int visited[MAXVEX];
//这里新增队列的代码
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;
}
void CreateMGraph(MGraph* G)
{
	int i, j, k;
	printf("请输入顶点数和边数\n");
	scanf("%d%d", &G->vexnum, &G->edgenum);
	printf("请输入顶点信息\n");
	//数组顶点信息(结点)
	for (i = 0; i < G->vexnum; i++)
	{
		scanf("%d", &G->vexs[i]);
	}
	//初始化邻接矩阵的二维数组
	for (i = 0; i < G->vexnum; i++)
	{
		for (j = 0; j < G->vexnum; j++)
		{
			G->matrix[i][j] = 0;
		}
	}
	printf("请输入边的信息\n");
	for (k = 0; k < G->edgenum; k++)
	{
		printf("请输入边（vi，vj）的下标i，下标j\n");
		scanf("%d%d", &i, &j);
		G->matrix[i][j] = 1;
		G->matrix[j][i] = 1;
	}
}
void BFS(MGraph* G,int v)
{
	Queue Q;
	InitQueue(&Q);
	visited[v] = 1;
	enQueue(&Q, v);
	while (!QueueEmpyt(&Q))
	{
		int currentVertex = deQueue(&Q);
		printf("%d ", currentVertex);
		for (int i = 0; i < G->vexnum; i++)
		{
			if (G->matrix[currentVertex][i] == 1 && visited[i] == 0)
			{
				visited[i] = 1;
				enQueue(&Q, i);
			}
		}
	}
}
void BFSTraverse(MGraph* G)
{
	int i;
	for (i = 0; i < G->vexnum; i++)
	{
		visited[i] = 0;
	}
	for (i = 0; i < G->vexnum; i++)
	{
		if (visited[i] == 0)
		{
			BFS(&G,i);
		}
	}
}
int main()
{
	MGraph G;
	CreateMGraph(&G);
	printf("广度优先搜索遍历如下\n");
	BFSTraverse(&G);
	return 0;
}

 上图代码是无向图的代码

无向图的连通图终端输入如下:

请输入顶点数和边数
8 7
请输入顶点信息
0 1 2 3 4 5 6 7
请输入边的信息
请输入边（vi，vj）的下标i，下标j
0 1
请输入边（vi，vj）的下标i，下标j
0 2
请输入边（vi，vj）的下标i，下标j
1 3
请输入边（vi，vj）的下标i，下标j
1 4
请输入边（vi，vj）的下标i，下标j
3 7
请输入边（vi，vj）的下标i，下标j
2 5
请输入边（vi，vj）的下标i，下标j
2 6
广度优先搜索遍历如下
0 1 2 3 4 5 6 7

图片如下: 

无向图的非连通图终端输入: 

请输入顶点数和边数
8 6
请输入顶点信息
0 1 2 3 4 5 6 7
请输入边的信息
请输入边（vi，vj）的下标i，下标j
0 1
请输入边（vi，vj）的下标i，下标j
1 3
请输入边（vi，vj）的下标i，下标j
1 4
请输入边（vi，vj）的下标i，下标j
3 7
请输入边（vi，vj）的下标i，下标j
2 5
请输入边（vi，vj）的下标i，下标j
2 6
广度优先搜索遍历如下
0 1 2 3 4 5 6 7

 

有向图的代码只需要修改如下:

	printf("请输入边的信息\n");
	for (k = 0; k < G->edgenum; k++)
	{
		printf("请输入边（vi，vj）的下标i，下标j\n");
		scanf("%d%d", &i, &j);
		G->matrix[i][j] = 1;
	}

因为有向图不是对称 对于邻接矩阵代码实现来说， 所以不需要G->marrix[j][i] = 1;

有向图的终端输入:

请输入顶点数和边数
4 3
请输入顶点信息
0 1 2 3
请输入边的信息
请输入边（vi，vj）的下标i，下标j
0 1
请输入边（vi，vj）的下标i，下标j
0 2
请输入边（vi，vj）的下标i，下标j
2 3
广度优先搜索遍历如下
0 1 2 3