php算法學習之寬度優先搜索
寬度優先搜索又稱廣度優先搜索,簡稱bfs。下面小編為大家整理了php算法學習之寬度優先搜索,希望能幫到大家!
搜索的方式是:從一個點開始,逐層的遍歷訪問周圍的點。比如有一個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個島。
思路:遍歷圖,只要找到一個島,就對這個島進行寬搜,把和它相鄰的所有島都找出來並且標記,這樣一個大島就找到了。當整個圖被遍歷後,也就找到了所有大島的個數。
2、給定一個矩陣,2代表牆,1代表殭屍,0代表人。殭屍每天可以將上下左右與之相鄰的人咬成殭屍,但是殭屍不能穿牆。求將所有的人變為殭屍需要幾天,如果不能全部變為殭屍返回-1.
0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
思路:首先我們應該統計出當前的人數,然後將圖中所有殭屍座標加入隊列,對隊列中的點進行搜索,每遍歷一層增加一天(很重要),搜索過程中遇到人就將人數-1。最後看人數如果歸零,證明全部變為殭屍,返回天數,否則返回-1.
-
php格式輸出文件var-export函數
php格式輸出文件var_export函數,以實例形式講述了格式輸出函數var_export的特性與具體用法,具有一定的參考借鑑價值,需要的朋友可以參考下.本文實例講述了php格式輸出文件var_export函數的用法。分享給大家供大家參考。具體如下:var_export:php4>=4.2.0,php5var...
-
php怎麼生成隨機密碼
使用PHP開發應用程序,尤其是網站程序,常常需要生成隨機密碼,如用户註冊生成隨機密碼,用户重置密碼也需要生成一個隨機的密碼。隨機密碼也就是一串固定長度的字符串,下面小編收集整理了幾種生成隨機字符串的'方法,以供大家參考。方法一:1、在33–126中生成一個隨機整...
-
PHP與.NET的區別
PHP跟,一個面向個人(php),一個面向大型系統(當然,做小系統也是可以的,只是資源佔用相對比較多小點)離旗鼓相當還有很遠.現在真正在台面上競爭的只有以java為開發語言的J2EE平台和以C#為代表,多語言的平台.下面小編給大家整理了PHP與的區別,供大家參閲。世界上最...
-
PHP常用開發技巧
PHP開發常用技巧能使你在開發過程中快而有效.以下就是小編精心推薦PHP常用開發技巧,希望對大家有幫助!1使用dowhile避免多層if語句嵌套我們直接舉例説明:實現方式①if($name=='hedong'){if($sex=='male'){if($major=='PHP'){$ret='...