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

更新時(shí)間：2019年10月19日 10:34:23 作者：水滴月

這篇文章主要介紹了python實(shí)現(xiàn)廣度優(yōu)先搜索過程解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

廣度優(yōu)先搜索

適用范圍：無(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)中找到芒果銷售商的問題
#使用字典表示映射關(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 = [] #記錄用于檢查過的人
   while search_queue: #只要隊(duì)列不為空
     person = search_queue.popleft() #就取出其中的第一個(gè)人
     if not person in searched: #這個(gè)人沒有被檢查過
       if is_target_node(person): #判斷這個(gè)人是否是要查找的銷售商
         print(person + " is target node!")
         return True
       else:
         search_queue += graph[person] #如果這個(gè)人不是，就將這個(gè)人的朋友壓入隊(duì)列
         searched.append(person) #將這個(gè)人追加到已檢查過的字典中
   return False

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

Python File(文件) 方法整理
在本篇文章中我們給大家整理了關(guān)于Python File(文件) 的用法以及相關(guān)知識(shí)點(diǎn)，有興趣的朋友們學(xué)習(xí)下。
2019-02-02
Django的Modelforms用法簡(jiǎn)介
這篇文章主要介紹了Django的Modelforms用法簡(jiǎn)介,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2019-07-07
python 如何將數(shù)據(jù)寫入本地txt文本文件的實(shí)現(xiàn)方法
這篇文章主要介紹了python 如何將數(shù)據(jù)寫入本地txt文本文件的實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2019-09-09
Python 數(shù)值區(qū)間處理_對(duì)interval 庫(kù)的快速入門詳解
今天小編就為大家分享一篇Python 數(shù)值區(qū)間處理_對(duì)interval 庫(kù)的快速入門詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2018-11-11
Python 數(shù)據(jù)可視化pyecharts的使用詳解
這篇文章主要介紹了Python 數(shù)據(jù)可視化pyecharts的使用詳解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2019-06-06
python數(shù)據(jù)預(yù)處理 :樣本分布不均的解決(過采樣和欠采樣)
今天小編就為大家分享一篇python數(shù)據(jù)預(yù)處理 :樣本分布不均的解決(過采樣和欠采樣)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2020-02-02
Python利用pywin32庫(kù)實(shí)現(xiàn)將PPT導(dǎo)出為高清圖片
這篇文章主要為大家詳細(xì)介紹了Python如何利用pywin32庫(kù)實(shí)現(xiàn)將PPT導(dǎo)出為高清圖片的功能，文中的示例代講解詳細(xì)，感興趣的小伙伴可以了解一下
2023-01-01
使用Python獲取字典鍵對(duì)應(yīng)值的兩種方法
對(duì)于字典通過鍵獲得值非常簡(jiǎn)單,但通過值獲得鍵則需繞些彎子,下面這篇文章主要給大家介紹了關(guān)于如何使用Python獲取字典鍵對(duì)應(yīng)值的相關(guān)資料,需要的朋友可以參考下
2022-04-04
如何使用Python實(shí)現(xiàn)CartPole游戲
在深度強(qiáng)化學(xué)習(xí)內(nèi)容的介紹中,提出了CartPole游戲進(jìn)行深度強(qiáng)化學(xué)習(xí),現(xiàn)在提供一種用Python簡(jiǎn)單實(shí)現(xiàn)Cart Pole游戲的方法,感興趣的朋友跟隨小編一起看看吧
2024-07-07
Python動(dòng)態(tài)生成多維數(shù)組的方法示例
這篇文章主要介紹了Python動(dòng)態(tài)生成多維數(shù)組的方法,涉及Python數(shù)組動(dòng)態(tài)遍歷、添加、打印等相關(guān)操作技巧,需要的朋友可以參考下
2018-08-08