python實(shí)現(xiàn)廣度優(yōu)先搜索過(guò)程解析-創(chuàng)新互聯(lián)

廣度優(yōu)先搜索

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專(zhuān)注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、微信小程序、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶(hù)創(chuàng)新互聯(lián)還提供了敦煌免費(fèi)建站歡迎大家使用！

適用范圍： 無(wú)權(quán)重的圖，與深度優(yōu)先搜索相比，深度優(yōu)先搜索法占內(nèi)存少但速度較慢，廣度優(yōu)先搜索算法占內(nèi)存多但速度較快

復(fù)雜度： 時(shí)間復(fù)雜度為O(V+E),V為頂點(diǎn)數(shù)，E為邊數(shù)

思路

廣度優(yōu)先搜索是以層為順序,將某一層上的所有節(jié)點(diǎn)都搜索到了之后才向下一層搜索；

代碼

from collections import deque

#解決從你的人際關(guān)系網(wǎng)中找到芒果銷(xiāo)售商的問(wèn)題
#使用字典表示映射關(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"] = []

#判斷是否是要查找的目標(biāo) 
def is_target_node(name):
   return name[-1] == 'm'

#實(shí)現(xiàn)廣度優(yōu)先搜索算法 
def search(name):
   search_queue = deque() #創(chuàng)建一個(gè)隊(duì)列
   search_queue += graph[name] 
   searched = [] #記錄用于檢查過(guò)的人
   while search_queue: #只要隊(duì)列不為空
     person = search_queue.popleft() #就取出其中的第一個(gè)人
     if not person in searched: #這個(gè)人沒(méi)有被檢查過(guò)
       if is_target_node(person): #判斷這個(gè)人是否是要查找的銷(xiāo)售商
         print(person + " is target node!")
         return True
       else:
         search_queue += graph[person] #如果這個(gè)人不是，就將這個(gè)人的朋友壓入隊(duì)列
         searched.append(person) #將這個(gè)人追加到已檢查過(guò)的字典中
   return False

#調(diào)用方法
search("you")

新聞標(biāo)題：python實(shí)現(xiàn)廣度優(yōu)先搜索過(guò)程解析-創(chuàng)新互聯(lián)
URL鏈接：http://www.muchs.cn/article2/depeoc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、Google、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站收錄、商城網(wǎng)站、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)