【算法】搜索入门-BFS

BFS

队列实现

1. 初始时，起点（即1号节点）入队。
2. 每次取出队首元素，从当前元素访问下一层元素(相当于树中子节点)，找到可行
   的元素后，加入队尾。
3. 重复操作2，直到队列为空。

考虑遍历一棵树所有节点：

采用DFS进行遍历：
1->2->4->2->5->2->1->3->6->3->7->3->1
对于上例：
q中元素：
执行操作1： {1}
执行操作2： 取出队首元素1： {}，从1扩展找到可行元素加入队尾： {2,3}
执行操作2： 取出队首元素2： {3}，从2扩展找到可行元素加入队尾： {3,4,5}
执行操作2： 取出队首元素3： {4,5}，从3扩展找到可行元素加入队尾： {4,5,6,7}
执行操作2： 取出队首元素4： {5,6,7}，从4扩展找到可行元素加入队尾： {5,6,7}
执行操作2： 取出队首元素5： {6,7}，从5扩展找到可行元素加入队尾： {6,7}
执行操作2： 取出队首元素6： {7}，从6扩展找到可行元素加入队尾： {7}
执行操作2： 取出队首元素4： {}，从7扩展找到可行元素加入队尾： {}
队列为空，结束BFS。

二叉树遍历

马的遍历

按照BFS框架，起点入队。此题中起点时坐标，如何入队呢？

双向BFS

与BFS唯一区别：从起点和终点一起遍历。
优点是显然的： BFS搜索过程中，随着深度不断增加，每层扩展的元素通常是递增的，这样会使无用状态越来越多，从起点和终点一起搜索，能有效减少无用状态的增加。

走迷宫

八数码难题

状压搜索

	对于一个矩阵只有9个数字，我们可以将这个矩阵转换成一个9位的数字，
或者通过进制的思想，转换成一个3进制数字。
	接着与双向BFS结合在一起即可。

砝码称重

虫食算