php算法學(xué)習(xí)之寬度優(yōu)先搜索

　　寬度優(yōu)先搜索又稱廣度優(yōu)先搜索，簡稱bfs。下面小編為大家整理了php算法學(xué)習(xí)之寬度優(yōu)先搜索，希望能幫到大家！

　　搜索的方式是：從一個(gè)點(diǎn)開始，逐層的遍歷訪問周圍的點(diǎn)。比如有一個(gè)5*5的矩陣，每次可以訪問某個(gè)點(diǎn)周圍所有八個(gè)點(diǎn)，則如果從中心點(diǎn)開始寬度搜索，只需兩層即可遍歷完整個(gè)矩陣。

　　寬度搜索可用于對(duì)樹、圖、矩陣等進(jìn)行搜索，適合用于求最短路徑等問題。

　　算法關(guān)鍵詞：隊(duì)列，利用隊(duì)列先進(jìn)先出的特點(diǎn)。隊(duì)列中存儲(chǔ)待遍歷的點(diǎn)，如果隊(duì)列不空，就從隊(duì)列中取出第一個(gè)元素，將此元素標(biāo)記為已訪問，再把與這個(gè)元素相鄰的未被標(biāo)記的元素添加到隊(duì)列末尾，循環(huán)直到隊(duì)列變?yōu)榭铡�從某個(gè)點(diǎn)開始搜索，只需要先把這個(gè)點(diǎn)添加到隊(duì)列中，然后開始遍歷的操作。

　　個(gè)人覺得寬度優(yōu)先搜索還是很容易學(xué)的，因?yàn)樗�的思想容易理解，而且寫的套路很固定�?/p>

　　實(shí)際應(yīng)用：爬蟲。爬蟲一般是首先將幾個(gè)母站添加到爬蟲隊(duì)列；然后從隊(duì)列中取出要爬的網(wǎng)站，分析網(wǎng)頁中包含的鏈接，將鏈接添加到爬蟲隊(duì)列，再爬取網(wǎng)站內(nèi)容；不斷往復(fù)這個(gè)操作，這和寬度搜索的執(zhí)行方式幾乎是一樣的。

　　下面做幾道題來練習(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)行寬搜，把和它相鄰的所有島都找出來并且標(biāo)記，這樣一個(gè)大島就找到了。當(dāng)整個(gè)圖被遍歷后，也就找到了所有大島的個(gè)數(shù)。

　　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

　　思路：首先我們應(yīng)該統(tǒng)計(jì)出當(dāng)前的人數(shù)，然后將圖中所有僵尸坐標(biāo)加入隊(duì)列，對(duì)隊(duì)列中的點(diǎn)進(jìn)行搜索，每遍歷一層增加一天（很重要），搜索過程中遇到人就將人數(shù)-1。最后看人數(shù)如果歸零，證明全部變?yōu)榻┦�，返回天�?shù)，否則返回-1.

【php算法學(xué)習(xí)之寬度優(yōu)先搜索】相關(guān)文章：

php算法學(xué)習(xí)之動(dòng)態(tài)規(guī)劃04-01

php學(xué)習(xí)之php配置07-15

php經(jīng)典算法介紹02-26

PHP經(jīng)典算法題03-19

PHP紅包算法04-06

PHP算法學(xué)習(xí)之分治法02-14

php學(xué)習(xí)之php預(yù)定義變量07-29

PHP的樹形結(jié)構(gòu)算法07-06

PHP幾個(gè)經(jīng)典算法題02-12