第六章 廣度優(yōu)先搜索
廣度優(yōu)先搜索算法 (英文: Breadth-First-Search, 縮寫為BFS), 又稱寬度優(yōu)先搜索, 或橫向優(yōu)先搜索, 是一種圖形搜索算法逞频。 簡單的說, BFS 是從根節(jié)點(diǎn)開始, 沿著樹的寬度遍歷樹的節(jié)點(diǎn)持钉。 如果所有節(jié)點(diǎn)均被訪問, 則算法終止菇绵。 廣度優(yōu)先搜索的實(shí)現(xiàn)是一般采用 open-closed 表
[圖片上傳失敗...(image-28dbd4-1527845362464)]
書中列舉了好幾個(gè)例子來講述什么是廣度優(yōu)先搜索, 講的很容易理解的馏予。
芒果銷售商問題复斥。 目標(biāo)是在你的人際關(guān)系網(wǎng)找到一位芒果銷售商, 如果 A 不是芒果銷售商, 就將他的朋友也加入到查找名單中霉旗。 也就意味著你將在他的朋友召川、 朋友的朋友等中查找南缓。 使用這種算法將遍歷你的整個(gè)人際關(guān)系網(wǎng), 直到找到芒果銷售商。 這就是廣度優(yōu)先搜索算法
# coding: utf-8
"""
這是書中芒果銷售商問題
名字中以`m`結(jié)尾的是銷售商
"""
from collections import deque
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"] = []
def search(name):
search_deque = deque()
search_deque += graph[name]
searched = []
while searched:
person = search_deque.popleft()
if person is not searched:
if person_is_seller(person):
print('Person' + person + 'is a mango seller')
return True
else:
search_deque += graph[person]
searched.append(person)
return False
def person_is_seller(name):
return name[-1] == 'm'
print(search('you'))
隊(duì)列
隊(duì)列是先進(jìn)先出, 棧是先進(jìn)后出
小結(jié)
- 廣度優(yōu)先搜索指出是否有從A到B的路徑, 如果有廣度優(yōu)先搜索將找出最短路徑
- 對(duì)于尋找最短路徑問題, 可使用圖來建模, 再使用廣度優(yōu)先搜索來解決問題
- 對(duì)于檢查過的人, 不需要再去檢查了, 否則可能導(dǎo)致無限循環(huán)
