运维开发网

python实现广度优先搜索

运维开发网 https://www.qedev.com 2020-07-17 19:14 出处:网络 作者:运维开发网整理
from collections import deque#解决从你的人际关系网中找到芒果销售商的问题#使用字典表示映射关系graph = {} graph[\"you\"] = [\"alice\", \"bob\", \"claire\"] graph[\"bob\"] = [\"anuj\", \"peggy\"] graph[\
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 is_target_node(name):

return name[-1] == ‘m‘

#实现广度优先搜索算法

def search(name):

search_queue = deque() #创建一个队列

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

#调用方法

search("you")

0

精彩评论

暂无评论...
验证码 换一张
取 消