Create a gist now

Instantly share code, notes, and snippets.

@changyuheng /bfs.py
Last active Aug 29, 2015

What would you like to do?
BFS
# Ref. http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
def bfs(graph, queue, visited=None):
if visited is None:
visited = set()
if not queue:
return
start = queue.pop(0)
yield start
visited.add(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:
return
(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