广度优先搜索算法BFS讲解以及python 实现
一.圖簡介
假設你居住在舊金山，要從雙子峰前往金門大橋，你想乘公交車前往。
為找出換乘最少的乘車路線，你將使用怎樣的算法？
金門大橋未突出，因此一步無法到達那里。兩步能嗎？
金門大橋未突出，兩步步無法到達那里。三步能嗎？
金門大橋突出了!因此從雙子峰出發(fā)，可沿下面的路線三步到達金門大橋。
還有其他前往金門大橋的路線，但他們更遠（需要四步）。這個算法發(fā)現(xiàn)，前往金門大橋的最短路徑需要三步，這種問題被稱為最短路徑問題。
解決最短路徑的算法被稱為廣度優(yōu)先搜索。
需要兩個步驟：
1圖
圖模擬一組連接。假設你和你朋友正在玩牌，模擬下誰欠誰錢。
Alex欠Rama錢，Tom欠Adit錢，等等。圖由節(jié)點(node)和邊（edge）組成。
圖由節(jié)點和邊組成。一個節(jié)點可以由眾多節(jié)點直接相連組成。這些節(jié)點被稱為鄰居。在前面的欠錢圖中，Rama是Alex的鄰居，Adit不是Alex的鄰居,因為它們不直接相連，但Adit是Rama的鄰居，又是Tom的鄰居。
二.廣度優(yōu)先搜索
廣度優(yōu)先搜索通常用來解決兩類問題：
算例
本文通過算法來解決問題1。
假設你經(jīng)營著一個芒果農(nóng)場，需要尋找芒果銷售商，以便將這些芒果賣給他。為此你可以在你的朋友中查找。
首先創(chuàng)建一個朋友名單，然后依次檢查名單中的每一個人，看他是不是芒果銷售商。
假設你的朋友沒有人是芒果銷售商，你必須在朋友的朋友中尋找。
檢查名單中的每個人時，你都將其朋友加入名單
這樣一來，你不僅在朋友中查找，還在朋友的朋友中查找。
上文解釋了如何解決問題1，下面講解如何通過算法來解決問題2。
誰是最近的芒果銷售商，例如，朋友是一度關系，朋友的朋友是二度關系。
在你看來，一度關系勝過二度關系，首先在一度關系里尋找，如果沒有芒果銷售商，再在二度關系里尋找，以此類推。
廣度優(yōu)先搜索就是這樣干的，首先檢查一度關系，再檢查二度關系。
在本題中，你可以這樣理解，一度關系先于二度關系加入名單。你按順序檢查名單中的每一個人，看他是不是芒果銷售商，然后再在二度關系里找。
本題需要運用到一個知識點：隊列
隊列是一種數(shù)據(jù)結構，具有先進先出的特點。例如排隊上車，排在前面的先上車。
三.代碼實現(xiàn)
1. 使用圖來建立問題模型。
首先，需要用代碼來實現(xiàn)圖。圖是有節(jié)點和鄰近節(jié)點組成。來表示 [我：余登武] ,[我的鄰居：小明，小白] 這種映射關系。這需要用到散列表。
散列表可以將鍵映射到值，在這里，將你映射到你的朋友。
python中用字典表示散列表。
graph={} graph['you']=["alice","bob","claire"]更大的圖
2.使用廣度優(yōu)先搜索解決問題
算法流程
流程中用到了隊列。隊列是一種數(shù)據(jù)結構，具有先進先出的特點。例如排隊上車，排在前面的先上車。python中采用deque來創(chuàng)建一個隊列。
代碼
#!/usr/bin/env python3 # -*- coding: utf-8 -*- # @Author: yudengwu(余登武） # @Date : 2021/1/04 #@email:1344732766@qq.com#定義圖 graph={} graph['you']=["alice","bob","claire"] graph['bob']=["anuj","peggy"] graph['alice']=["peggy"] graph['claire']=["thom","jonny"] graph['anuj']=[] graph['peggy']=[] graph['thom']=[] graph['jonny']=[]#檢查是否是芒果銷售商。如果名字最后一個字母為m就是芒果銷售商 def person_is_seller(name):return name[-1] =='m'#from collections import deque #導入隊列 search_deque=deque()#創(chuàng)建一個隊列 search_deque+=graph['you'] #print(search_deque) #deque(['alice', 'bob', 'claire'])#檢查部分代碼 try:while search_deque: # 只有隊列不為空find = False # 定義是否找到person = search_deque.popleft() # 取出隊列中的第一個人if person_is_seller(person):print(person + "是芒果銷售商")find = Truebreakelse:search_deque += graph[person] # 將朋友的朋友添加進隊列 finally:if find==False:print('沒有找到')運行結果
該段代碼終止條件：
代碼優(yōu)化
代碼優(yōu)化
peggy既是Alice的朋友又是Bob的朋友，因此她將被加入隊列兩次：一次是在添加Alice的朋友時，一次是在添加Bob的朋友時。因此搜索隊列里包含了兩個peggy。
我們可以只檢查peggy一次，檢查完一個人后，標記這個人為已檢查。且不再檢查他。如果不這樣做，很快可能陷入死循環(huán)，如果你的朋友關系如圖。
最后代碼
#定義圖，圖中每個人的朋友關系都要寫 graph={} graph['you']=["alice","bob","claire"] graph['bob']=["anuj","peggy"] graph['alice']=["peggy"] graph['claire']=["thom","jonny"] graph['anuj']=[] graph['peggy']=[] graph['thom']=[] graph['jonny']=[]#檢查是否是芒果銷售商。如果名字最后一個字母為m就是芒果銷售商 def person_is_seller(name):return name[-1] =='m'#檢查是否是芒果商代碼from collections import deque #導入隊列 search_deque=deque()#創(chuàng)建一個隊列def search(name):search_deque = deque() # 創(chuàng)建一個隊列search_deque += graph[name]#將一級關系添加進隊列，即自己的朋友searched=[]#定義是否檢查try:while search_deque: # 只有隊列不為空find = False # 定義是否找到person = search_deque.popleft() # 取出隊列中的第一個人if person not in searched:#如果這個人沒有被檢查if person_is_seller(person):#如果這個人是芒果商print(person + "是芒果銷售商")find = Truebreakelse: #如果不是芒果商search_deque += graph[person] # 將朋友的朋友添加進隊列searched.append(person)#將這個人標記為已檢查finally:if find == False:print('沒有找到')search('you')運行結果
打印最短路徑
在上文中，我們找到了芒果供應商是thom，我們現(xiàn)在需要把you到thom的關系打印出來。
我這里采用倒排表的知識來實現(xiàn)
假設
原始字典為
{‘問題IID’:[關鍵詞1,關鍵詞2…],‘問題2ID’:[關鍵詞2,關鍵詞3…]…}
處理后的倒排表為
{‘關鍵詞1’:[問題1ID],‘關鍵詞2’:[問題1ID，問題2ID…}
本文有借鑒書籍《算法圖解》
作者：電氣-余登武
總結
以上是生活随笔為你收集整理的广度优先搜索算法BFS讲解以及python 实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 结构性存款是理财吗
- 下一篇： 基金定投有什么优势和劣势 注意这几点就