'''
The program is copied from the following website
http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
2017-10-04
Xiannong Meng
'''
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

print('from A to F')
print(list(bfs_paths(graph, 'A', 'F'))) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

print('from D to F')
print(list(bfs_paths(graph, 'D', 'F'))) # [['D', 'B', 'E', 'F'], ['D', 'B', 'A', 'C', 'F']]

print('from D to C')
print(list(bfs_paths(graph, 'D', 'C'))) # [['D', 'B', 'A', 'C'], ['D', 'B', 'E', 'F', 'C']]