In [9]:
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 is a seller return it. Done.
if person_is_seller(n):
return n
visited[n] = True
# append node's unvisited friends to the queue
#queue.extend([k for k in graph[n] if k not in visited])
queue.extend(filter(lambda x: x not in visited, graph[n]))
return None
BFS("you")
Out[9]:
In [ ]: