广度优先搜索(BFS)

1.基本思想

广度优先搜索(Breadth-First-Search,BFS)可以使用队列(queue)来实现，整个过程也可以看做一个倒立的树形： 1、把根节点放到队列的末尾。 2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。 3、找到所要找的元素时结束程序。 4、如果遍历整个树还没有找到，结束程序。（来自百度百科）

2.代码实现（C++）

#include 
#include 
#include 
#include 
#define ElemType int
#define MaxSize 1000

//定义图的结点数
const int Node = 5; 

using namespace std;

//定义顺序队列
typedef struct{
	ElemType data[MaxSize];
	//队头和队尾指针 
	int front,rear; 
}SqQueue; 

//初始化环形队列
void InitQueue(SqQueue * &q){
	q=(SqQueue *)malloc(sizeof(SqQueue));
	q->front=q->rear=0;
} 

//进队列
bool enQueue(SqQueue * &q,ElemType e){
	if((q->rear+1)%MaxSize==q->front){
		return false;
	}else{
		q->rear=(q->rear+1)%MaxSize;
		q->data[q->rear]=e;
		return true;
	}
} 

//出队列
bool deQueue(SqQueue * &q,ElemType &e){
	if(q->front==q->rear){
		return false;
	}else{
		q->front=(q->front+1)%MaxSize;
		e=q->data[q->front];
		return true;
	}
} 

//判断队列是否为空 
bool QueueEmpty(SqQueue *q){
	return (q->front==q->rear);
}

void BFS(int arr[Node][Node], int k){
	int w;
	//定义环形队列指针 
	SqQueue *qu;
	InitQueue(qu);
	int visited[MaxSize];
	memset(visited,0,sizeof(visited));
	cout