欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python實現(xiàn)廣度優(yōu)先搜索過程解析

 更新時間：2019年10月19日 10:34:23   作者：水滴月  
這篇文章主要介紹了python實現(xiàn)廣度優(yōu)先搜索過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

廣度優(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"] = []

#判斷是否是要查找的目標(biāo) 
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í)有所幫助，也希望大家多多支持腳本之家。

相關(guān)文章

最新評論