python实现广度优先搜索
哈哈
阅读:915
2020-02-19 11:32:09
评论:0
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")
声明
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。