bfs.py
源码如下:
# -*- coding: utf-8 -*
# 广度优先搜索算法
# import bfs
# graph ={}
# graph = bfs.create_data2()
# bfs.search(graph,'you')
def create_data2():
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"]=[]
return graph
def person_is_seller(name):
return name[-1] == 'm'
def search(graph,name):
from collections import deque #引入对接模块
search_queue=deque()#创建一个队列
search_queue+=graph[name]
searched=[]
while search_queue:
person=search_queue.popleft()
if not person in searched :
if person_is_seller(person):
print person +" is a mango"
return True
else:
search_queue+=graph[person]
searched.append(person)
return False
执行结果: