宽度优先搜索又称广度优先搜索，简称bfs。
搜索的方式是：从一个点开始，逐层的遍历访问周围的点。比如有一个5*5的矩阵，每次可以访问某个点周围所有八个点，则如果从中心点开始宽度搜索，只需两层即可遍历完整个矩阵。
宽度搜索可用于对树、图、矩阵等进行搜索，适合用于求最短路径等问题。
算法关键词：队列，利用队列先进先出的特点。队列中存储待遍历的点，如果队列不空，就从队列中取出第一个元素，将此元素标记为已访问，再把与这个元素相邻的未被标记的元素添加到队列末尾，循环直到队列变为空。从某个点开始搜索，只需要先把这个点添加到队列中，然后开始遍历的操作。
个人觉得宽度优先搜索还是很容易学的，因为它的思想容易理解，而且写的套路很固定。
实际应用：爬虫。爬虫一般是首先将几个母站添加到爬虫队列；然后从队列中取出要爬的网站，分析网页中包含的链接，将链接添加到爬虫队列，再爬取网站内容；不断往复这个操作，这和宽度搜索的执行方式几乎是一样的。
下面做几道题来练习：
1、给一个01矩阵，求不同的岛屿的个数。0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
样例
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
上图矩阵有3个岛。
思路：遍历图，只要找到一个岛，就对这个岛进行宽搜，把和它相邻的所有岛都找出来并且标记，这样一个大岛就找到了。当整个图被遍历后，也就找到了所有大岛的个数。
<?php
class Coor {
public $x;
public $y;
function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
}
function numIslands($grid) {
if (!$grid || sizeof($grid) == 0 || sizeof($grid[0]) == 0) {
return 0;
}
$n = sizeof($grid);
$m = sizeof($grid[0]);
$num = 0;//岛屿个数
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
if ($grid[$i][$j]) {
//搜索和这个岛相邻的所有岛
bfs($grid, $i, $j);
$num++;
}
}
}
return $num;
}
function bfs(&$grid, $x, $y) {
$directX = [-1, 0, 1, 0];
$directY = [0, 1, 0, -1];
$queue = [];
array_push($queue, new Coor($x, $y));
$gird[$x][$y] = false;//将已访问的标记
while ($queue) {
$tmpCor = array_shift($queue);
for ($i = 0; $i < 4; $i++) {
$tx = $tmpCor->x + $directX[$i];
$ty = $tmpCor->y + $directY[$i];
//在边界内并且是岛屿
if (inBound($grid, $tx, $ty) && $grid[$tx][$ty]) {
array_push($queue, new Coor($tx, $ty));
$grid[$tx][$ty] = false;
}
}
}
}
function inBound($grid, $x, $y) {
$n = sizeof($grid);
$m = sizeof($grid[0]);
return $x >= 0 && $x < $n && $y >= 0 && $y < $m;
}
2、给定一个矩阵，2代表墙，1代表僵尸，0代表人。僵尸每天可以将上下左右与之相邻的人咬成僵尸，但是僵尸不能穿墙。求将所有的人变为僵尸需要几天，如果不能全部变为僵尸返回-1.
0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
如上图return 2。
思路：首先我们应该统计出当前的人数，然后将图中所有僵尸坐标加入队列，对队列中的点进行搜索，每遍历一层增加一天（很重要），搜索过程中遇到人就将人数-1。最后看人数如果归零，证明全部变为僵尸，返回天数，否则返回-1.
class Coor {
public $x;
public $y;
function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
}
function zombie($grid) {
if (!$grid || sizeof($grid) == 0 || sizeof($grid[0]) == 0) {
return 0;
}
$n = sizeof($grid);
$m = sizeof($grid[0]);
$people = 0;//人数
$day = 0;//天数
$queue = [];
//初始化已知条件
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
if ($grid[$i][$j] == 0) {
$people++;
}
if ($grid[$i][$j] == 1) {
array_push($queue, new Coor($i, $j));
}
}
}
//僵尸感染过程！！！
$directX = [-1, 0, 1, 0];
$directY = [0, 1, 0, -1];
while ($queue) {
$day++;
$cnt = sizeof($queue);
for ($i = 0; $i < $cnt; $i++) {
$cor = array_shift($queue);
for ($j = 0; $j < 4; $j++) {
$tx = $cor->x + $directX[$j];
$ty = $cor->y + $directY[$j];
if (inBound($grid, $tx, $ty) && $grid[$tx][$ty] == 0) {
$people--;
$grid[$tx][$ty] = 1;
array_push($queue, new Coor($tx, $ty));
}
}
}
if ($people == 0) {
return $day;
}
}
return -1;
}
function inBound($grid, $x, $y) {
$n = sizeof($grid);
$m = sizeof($grid[0]);
return $x >= 0 && $x < $n && $y >= 0 && $y < $m;
}
