寬度優(yōu)先搜索又稱廣度優(yōu)先搜索揽涮，簡(jiǎn)稱bfs猴娩。
搜索的方式是：從一個(gè)點(diǎn)開(kāi)始阴幌，逐層的遍歷訪問(wèn)周?chē)狞c(diǎn)勺阐。比如有一個(gè)5*5的矩陣，每次可以訪問(wèn)某個(gè)點(diǎn)周?chē)邪藗€(gè)點(diǎn)矛双，則如果從中心點(diǎn)開(kāi)始寬度搜索渊抽，只需兩層即可遍歷完整個(gè)矩陣。
寬度搜索可用于對(duì)樹(shù)议忽、圖懒闷、矩陣等進(jìn)行搜索，適合用于求最短路徑等問(wèn)題栈幸。
算法關(guān)鍵詞：隊(duì)列愤估，利用隊(duì)列先進(jìn)先出的特點(diǎn)。隊(duì)列中存儲(chǔ)待遍歷的點(diǎn)速址，如果隊(duì)列不空玩焰，就從隊(duì)列中取出第一個(gè)元素，將此元素標(biāo)記為已訪問(wèn)芍锚，再把與這個(gè)元素相鄰的未被標(biāo)記的元素添加到隊(duì)列末尾昔园，循環(huán)直到隊(duì)列變?yōu)榭铡哪硞€(gè)點(diǎn)開(kāi)始搜索并炮，只需要先把這個(gè)點(diǎn)添加到隊(duì)列中默刚，然后開(kāi)始遍歷的操作。
個(gè)人覺(jué)得寬度優(yōu)先搜索還是很容易學(xué)的逃魄，因?yàn)樗乃枷肴菀桌斫饣缥鳎覍?xiě)的套路很固定。
實(shí)際應(yīng)用：爬蟲(chóng)伍俘。爬蟲(chóng)一般是首先將幾個(gè)母站添加到爬蟲(chóng)隊(duì)列邪锌；然后從隊(duì)列中取出要爬的網(wǎng)站，分析網(wǎng)頁(yè)中包含的鏈接养篓，將鏈接添加到爬蟲(chóng)隊(duì)列秃流，再爬取網(wǎng)站內(nèi)容；不斷往復(fù)這個(gè)操作柳弄，這和寬度搜索的執(zhí)行方式幾乎是一樣的舶胀。
下面做幾道題來(lái)練習(xí)：
1、給一個(gè)01矩陣碧注，求不同的島嶼的個(gè)數(shù)嚣伐。0代表海，1代表島萍丐，如果兩個(gè)1相鄰轩端，那么這兩個(gè)1屬于同一個(gè)島。我們只考慮上下左右為相鄰逝变。
樣例
[
[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個(gè)島基茵。
思路：遍歷圖奋构，只要找到一個(gè)島，就對(duì)這個(gè)島進(jìn)行寬搜拱层，把和它相鄰的所有島都找出來(lái)并且標(biāo)記，這樣一個(gè)大島就找到了根灯。當(dāng)整個(gè)圖被遍歷后径缅，也就找到了所有大島的個(gè)數(shù)。
<?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;//島嶼個(gè)數(shù)
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $m; $j++) {
if ($grid[$i][$j]) {
//搜索和這個(gè)島相鄰的所有島
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;//將已訪問(wèn)的標(biāo)記
while ($queue) {
$tmpCor = array_shift($queue);
for ($i = 0; $i < 4; $i++) {
$tx = $tmpCor->x + $directX[$i];
$ty = $tmpCor->y + $directY[$i];
//在邊界內(nè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烙肺、給定一個(gè)矩陣纳猪，2代表墻，1代表僵尸桃笙，0代表人氏堤。僵尸每天可以將上下左右與之相鄰的人咬成僵尸，但是僵尸不能穿墻搏明。求將所有的人變?yōu)榻┦枰獛滋炖鲡绻荒苋孔優(yōu)榻┦祷?1.
0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
如上圖return 2。
思路：首先我們應(yīng)該統(tǒng)計(jì)出當(dāng)前的人數(shù)熏瞄，然后將圖中所有僵尸坐標(biāo)加入隊(duì)列，對(duì)隊(duì)列中的點(diǎn)進(jìn)行搜索谬以，每遍歷一層增加一天（很重要）强饮，搜索過(guò)程中遇到人就將人數(shù)-1。最后看人數(shù)如果歸零为黎，證明全部變?yōu)榻┦史幔祷靥鞌?shù)，否則返回-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;//人數(shù)
$day = 0;//天數(shù)
$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));
}
}
}
//僵尸感染過(guò)程Ｃ＜袅！
$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;
}
