- 相關推薦
php算法學習之寬度優(yōu)先搜索
寬度優(yōu)先搜索又稱廣度優(yōu)先搜索，簡稱bfs。下面小編為大家整理了php算法學習之寬度優(yōu)先搜索，希望能幫到大家！
搜索的方式是：從一個點開始，逐層的遍歷訪問周圍的點。比如有一個5*5的矩陣，每次可以訪問某個點周圍所有八個點，則如果從中心點開始寬度搜索，只需兩層即可遍歷完整個矩陣。
寬度搜索可用于對樹、圖、矩陣等進行搜索，適合用于求最短路徑等問題。
算法關鍵詞：隊列，利用隊列先進先出的特點。隊列中存儲待遍歷的點，如果隊列不空，就從隊列中取出第一個元素，將此元素標記為已訪問，再把與這個元素相鄰的未被標記的元素添加到隊列末尾，循環(huán)直到隊列變?yōu)榭铡哪硞�點開始搜索，只需要先把這個點添加到隊列中，然后開始遍歷的操作。
個人覺得寬度優(yōu)先搜索還是很容易學的，因為它的思想容易理解，而且寫的套路很固定。
實際應用：爬蟲。爬蟲一般是首先將幾個母站添加到爬蟲隊列；然后從隊列中取出要爬的網(wǎng)站，分析網(wǎng)頁中包含的鏈接，將鏈接添加到爬蟲隊列，再爬取網(wǎng)站內(nèi)容；不斷往復這個操作，這和寬度搜索的執(zhí)行方式幾乎是一樣的。
下面做幾道題來練習：
1、給一個01矩陣，求不同的島嶼的個數(shù)。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個島。
思路：遍歷圖，只要找到一個島，就對這個島進行寬搜，把和它相鄰的所有島都找出來并且標記，這樣一個大島就找到了。當整個圖被遍歷后，也就找到了所有大島的個數(shù)。
2、給定一個矩陣，2代表墻，1代表僵尸，0代表人。僵尸每天可以將上下左右與之相鄰的人咬成僵尸，但是僵尸不能穿墻。求將所有的人變?yōu)榻┦枰獛滋�，如果不能全部變�(yōu)榻┦祷?1.
0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
思路：首先我們應該統(tǒng)計出當前的人數(shù)，然后將圖中所有僵尸坐標加入隊列，對隊列中的點進行搜索，每遍歷一層增加一天（很重要），搜索過程中遇到人就將人數(shù)-1。最后看人數(shù)如果歸零，證明全部變?yōu)榻┦祷靥鞌?shù)，否則返回-1.
【php算法學習之寬度優(yōu)先搜索】相關文章：
PHP算法學習之分治法09-13
PHP的樹形結(jié)構(gòu)算法07-06
PHP快速排序算法詳解08-30
PHP實現(xiàn)抽獎概率算法09-13
php啟用sphinx全文搜索的方法07-27
PHP排序算法類講解07-18
PHP快速排序算法解析10-09