[本文是自己学习所做笔记，欢迎转载，但请注明出处：http://blog.csdn.net/jesson20121020]

算法描述：

          设图G的初始状态是所有顶点均未被访问过，在G中的任选一顶点vi为初始出发点，则广度优先遍历 可定义如下：首先，访问初始出发点vi，接着依次访问vi的所有邻接点w1,w2,...,wk;然后，依次访问w1,w2,...,wk 的邻接的所有未被访问过的顶点，依次类推，直到图中所有的和初始点vi有路径相通的顶点都被访问过为止。

算法实现：

           (1) 访问初始顶点vi

          (2) 置顶点v已访问标记

          (3) 顶点v入队

          (4) while(队不空)｛

                   取出队首顶点i；

                   依次搜索顶点i的所有的邻接点；

                   如果未被访问，则访问该邻接点，并将其入队。

           ｝

               用邻接矩阵实现图的广度优先遍历的源代码如下：

/**
 * 广度遍历图
 **/
void BFS_MG(MGraph MG,int s){
	//清空访问标志
	init_Visit();
	//定义队列，用于保存当前节点的邻接顶点
	int Q[MAX_VEX_NUM];
	int front = 0;
	int rear = 0;
	int i,j,k;
	printf("%c\t",MG.vexs[s]);
	visit[s] = 1;
	Q[rear++] = s;
	//遍历队列 
	while(front < rear){
		i = Q[front++];
		for (j = 1; j <= MG.vexnum;j++){
			if(visit[j] == 0 && MG.arcs[i][j] == 1){
				printf("%c\t",MG.vexs[j]);
				visit[j] = 1;
				Q[rear++] = j;
			}
			
		}
	}
}

         用邻接表实现图的广度优先遍历的源代码如下：

/**
 * 广度遍历图
 **/
void BFS_AG(ALGraph AG,int s){
	ArcPtr p;
	//清空访问标志
	init_Visit();
	//定义队列，用于保存当前节点的邻接顶点
	int Q[MAX_VERTEX_NUM];
	int front = 0;
	int rear = 0;
	int i,j,k;
	printf("%c\t",AG.vertices[s]);
	visit[s] = 1;
	Q[rear++] = s;
	//遍历队列 
	while(front < rear){
		i = Q[front++];
	for(p = AG.vertices[i].firstarc;p;p=p->nextarc){
			j = p->adjvex;
			if(visit[j] == 0){
				printf("%c\t",AG.vertices[j].vexdata);
				visit[j] = 1;
				Q[rear++] = j;
			}
			
		}
	}
}

算法说明：  

        对有具有n个顶点和e条边的连通图，因为每个基点均需要入队一次，所以while语句需要执行n次，对于邻接矩阵而言，内循环搜索邻接点时同样需要执行n次，故BFS_MG的时间复杂度为O(n^2)；对于邻接表而言，内循环的次数取决于各顶点的边表结点的总个数，所以BFS_AG的时间复杂度为O(n+e)。

        可以看出，广度优先遍历需要一个辅助队列，和标志数组，故空间复杂度为O(n)。

完整代码：

           用邻接矩阵实现广度优先遍历的完整代码：

/*
 ============================================================================
 Name        : Graph.c
 Author      : jesson20121020
 Version     : 1.0
 Description : create Graph using Adjacency Matrix, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#define MAX_VEX_NUM 50
typedef char VertexType;
typedef enum {
	DG, UDG
} GraphType;
typedef struct {
	VertexType vexs[MAX_VEX_NUM];
	int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
	int vexnum, arcnum;
	GraphType type;
} MGraph;

//设置图中顶点访问标志
int visit[MAX_VEX_NUM];

/**
 * 根据名称得到指定顶点在顶点集合中的下标
 * vex  顶点
 * return 如果找到，则返回下标，否则，返回０
 */
int getIndexOfVexs(char vex, MGraph *MG) {
	int i;
	for (i = 1; i <= MG->vexnum; i++) {
		if (MG->vexs[i] == vex) {
			return i;
		}
	}
	return 0;
}

/**
 * 创建邻接矩阵
 */
void create_MG(MGraph *MG) {
	int i, j, k;
	int v1, v2, type;
	char c1, c2;
	printf("Please input graph type DG(0) or UDG(1) :");
	scanf("%d", &type);
	if (type == 0)
		MG->type = DG;
	else if (type == 1)
		MG->type = UDG;
	else {
		printf("Please input correct graph type DG(0) or UDG(1)!");
		return;
	}

	printf("Please input vexmun : ");
	scanf("%d", &MG->vexnum);
	printf("Please input arcnum : ");
	scanf("%d", &MG->arcnum);
	getchar();
	for (i = 1; i <= MG->vexnum; i++) {
		printf("Please input %dth vex(char):", i);
		scanf("%c", &MG->vexs[i]);
		getchar();
	}

	//初始化邻接矩阵
	for (i = 1; i <= MG->vexnum; i++) {
		for (j = 1; j <= MG->vexnum; j++) {
			MG->arcs[i][j] = 0;
		}
	}

	//输入边的信息，建立邻接矩阵
	for (k = 1; k <= MG->arcnum; k++) {
		printf("Please input %dth arc v1(char) v2(char) : ", k);

		scanf("%c %c", &c1, &c2);
		v1 = getIndexOfVexs(c1, MG);
		v2 = getIndexOfVexs(c2, MG);
		if (MG->type == 1)
			MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
		else
			MG->arcs[v1][v2] = 1;
		getchar();
	}
}
/**
 * 打印邻接矩阵和顶点信息
 */
void print_MG(MGraph MG) {
	int i, j;
	if(MG.type == DG){
		printf("Graph type: Direct graph\n");
	}
	else{
		printf("Graph type: Undirect graph\n");
	}

	printf("Graph vertex number: %d\n",MG.vexnum);
	printf("Graph arc number: %d\n",MG.arcnum);

	printf("Vertex set:\n ");
	for (i = 1; i <= MG.vexnum; i++)
		printf("%c\t", MG.vexs[i]);
	printf("\nAdjacency Matrix:\n");

	for (i = 1; i <= MG.vexnum; i++) {
		j = 1;
		for (; j < MG.vexnum; j++) {
			printf("%d\t", MG.arcs[i][j]);
		}
		printf("%d\n", MG.arcs[i][j]);
	}
}

/**
 * 初始化顶点访问标志
 **/
void init_Visit(){
	int i;
	for(i = 0;i < MAX_VEX_NUM;i++)
		visit[i] = 0;
}

/**
 * 广度遍历图
 **/
void BFS_MG(MGraph MG,int s){
	//清空访问标志
	init_Visit();
	//定义队列，用于保存当前节点的邻接顶点
	int Q[MAX_VEX_NUM];
	int front = 0;
	int rear = 0;
	int i,j,k;
	printf("%c\t",MG.vexs[s]);
	visit[s] = 1;
	Q[rear++] = s;
	//遍历队列 
	while(front < rear){
		i = Q[front++];
		for (j = 1; j <= MG.vexnum;j++){
			if(visit[j] == 0 && MG.arcs[i][j] == 1){
				printf("%c\t",MG.vexs[j]);
				visit[j] = 1;
				Q[rear++] = j;
			}
			
		}
	}
}

/**
 * 主函数
 */
int main(void) {
	MGraph MG;
	create_MG(&MG);
	print_MG(MG);

	printf("\nThe result of BFS:\n");
	BFS_MG(MG,1);
	
	return EXIT_SUCCESS;
}

           用邻接表实现广度优先遍历的完整代码：

/*
 ============================================================================
 Name        : ALGraph.c
 Author      : jesson20121020
 Version     :
 Copyright   : Your copyright notice
 Description : Graph using linkList, Ansi-style
 ============================================================================
 */

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

#include <stdio.h>

#define MAX_VERTEX_NUM 50
typedef enum {
	DG, UDG
} GraphType;
typedef char VertexType;
//表节点
typedef struct ArcNode {
	int adjvex; //邻接节点
	int weight; //边权重
	struct ArcNode *nextarc; //下一个节点指针
} ArcNode, *ArcPtr;
//头节点
typedef struct {
	VertexType vexdata;
	int id;
	ArcPtr firstarc;
} VNode;
//头节点数组
typedef struct {
	VNode vertices[MAX_VERTEX_NUM];
	int vexnum, arcnum;
	GraphType type;
} ALGraph;

int visit[MAX_VERTEX_NUM];

/**
 * 根据顶点字符得到在顶点数组中的下标
 */
int getIndexOfVexs(char vex, ALGraph *AG) {
	int i;
	for (i = 1; i <= AG->vexnum; i++) {
		if (AG->vertices[i].vexdata =http://www.mamicode.com/= vex) {>


数据结构（C实现）------- 图的广度优先遍历