溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
廣度優(yōu)先搜索
適用范圍： 無權(quán)重的圖，與深度優(yōu)先搜索相比，深度優(yōu)先搜索法占內(nèi)存少但速度較慢，廣度優(yōu)先搜索算法占內(nèi)存多但速度較快
復(fù)雜度： 時間復(fù)雜度為O(V+E),V為頂點數(shù)，E為邊數(shù)
思路
廣度優(yōu)先搜索是以層為順序,將某一層上的所有節(jié)點都搜索到了之后才向下一層搜索；
代碼
from collections import deque
#解決從你的人際關(guān)系網(wǎng)中找到芒果銷售商的問題
#使用字典表示映射關(guā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"] = []
#判斷是否是要查找的目標
def is_target_node(name):
return name[-1] == 'm'
#實現(xiàn)廣度優(yōu)先搜索算法
def search(name):
search_queue = deque() #創(chuàng)建一個隊列
search_queue += graph[name]
searched = [] #記錄用于檢查過的人
while search_queue: #只要隊列不為空
person = search_queue.popleft() #就取出其中的第一個人
if not person in searched: #這個人沒有被檢查過
if is_target_node(person): #判斷這個人是否是要查找的銷售商
print(person + " is target node!")
return True
else:
search_queue += graph[person] #如果這個人不是，就將這個人的朋友壓入隊列
searched.append(person) #將這個人追加到已檢查過的字典中
return False
#調(diào)用方法
search("you")
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼