Breadth First Search

Find a mango seller.

Hint: her name should ends with 'm'

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

    # 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:
        # otherwise add it to the visited
            visited[n] = True

        # if it is a seller
        if person_is_seller(n):
            # return it
            return n
        # append node's friends to the queue

    return None


*you     alice   bob     claire 
*you    *alice   bob     claire  peggy  
*you    *alice  *bob     claire  peggy   anuj    peggy  
*you    *alice  *bob    *claire  peggy   anuj    peggy   thom    jonny  
*you    *alice  *bob    *claire *peggy   anuj    peggy   thom    jonny  
*you    *alice  *bob    *claire *peggy  *anuj    peggy   thom    jonny  
*you    *alice  *bob    *claire *peggy  *anuj    thom    jonny  

In [ ]: