广搜Bfs

// 起点是第0层，从起点最少需n步就能到达的点属于第n层  
// 广搜扩展节点。如果扩展时记住了父节点则是广搜寻路 

// 区分Dfs（本质上的区别在于Dfs是递归的，而Bfs不是递归的） 
Bfs() 
{
	initQueue(); //初始化队列q。队列元素为一个节点，当我们需要每个节点的层数时，将层数作为节点的属性。 
	while(!q.empty()) //队列不为空
	{
		if(q.front()==目标节点) //找到目标节点
		{
			break;
		} 
		//取队首节点扩展，扩展那些未访问过的节点，将它们放入队尾。有时候扩展节点时要记住父节点，也就是记住路径 
		略
		for U in 可扩展节点 :
			visited[U] = 1; //U已被访问过
			记录广搜层数（也就是从起点到U的最短路径）; 
		//扩展完节点之后扔掉队首节点
		q.pop();
	}
} 
//不使用queue而使用一维数组简单构造的队列时，能保留队首节点，见题目迷宫问题 

广搜与深搜的对比

广搜不是递归的，必须一层一层推进，因此会占用较大空间而且盲目性较大，无法剪枝。但也正因它不是递归的，而是层层推进的，所以是完备策略。

广搜解决递归函数 或者怎么说

对于一个递归函数，我们可以用搜索的方式解决。深搜的方法已经讲过：深搜Dfs遍历节点以及寻路
这里谈谈广搜。我们把问题看作在递归的状态图，这个图上进行广搜。有以下几点要注意：

1. 由于采用广搜的方法，所以要存储状态节点。那么，如何去存储递归函数的一个状态呢？
   通常，如果我们将递归函数抽象地以f(x1,x2,…,xn)表示，我们可以用数组存储，也就是像做动态规划那样；
   如果我们的问题确实是在一张地图上搜索寻路 1 静态地图 2 动态地图（能扩展的节点会变？）地图会变？ 地图是状态？走图的过程是递归的？八数码
2. List item