In [38]:
from collections import deque
def person_is_seller(name):
return name[-1] == 'm'
graph = {
"you": ["alice", "bob", "claire"],
"bob": ["anuj", "peggy"],
"alice": ["peggy"],
"claire": ["thom", "jonny"],
"anuj": [],
"peggy": [],
"thom": [],
"jonny": []
}
def to_str(a,s=''):
return "".join([s+'{0:7}'.format(v) for v in a])
def BFS(node):
"""
Find a person selling bananas.
"""
# a queue for nodes to explore
queue = []
# list of visited nodes
visited = {}
# add node to the queue
queue.append(node)
# while queue is not empty do:
while len(queue) > 0:
print(to_str(visited,'*') + to_str(queue,' '))
# remove the first element from the queue
n = queue.pop(0)
# if it's been visited skip the rest of the loop
if n in visited:
continue
# otherwise add it to the visited
else:
visited[n] = True
# if it is a seller
if person_is_seller(n):
# return it
return n
# append node's friends to the queue
queue.extend(graph[n])
return None
BFS("you")
Out[38]:
In [ ]: