Create a gist now

Instantly share code, notes, and snippets.

@changyuheng /
Last active Aug 29, 2015

# Ref.
def bfs(graph, queue, visited=None):
if visited is None:
visited = set()
if not queue:
start = queue.pop(0)
yield start
queue += [vertex for vertex in graph[start] - set(queue) - visited]
yield from bfs(graph, queue, visited=visited)
def bfs_paths(graph, queue, goal):
if not queue:
(start, path) = queue.pop(0)
if start == goal:
yield path
queue += [(vertex, path + [vertex]) for vertex in graph[start] - set(path)]
yield from bfs_paths(graph, queue, goal)
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']),
print(repr([vertex for vertex in bfs(graph, ['A'])]))
print(repr([path for path in bfs_paths(graph, [('A', ['A'])], 'F')]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment