JGuizard
5/1/2016 - 9:29 AM

## Example of Breath First Search (BFS) algorithm implementation in recursive and non-recursive mode, for graph expansion and path finding.

Example of Breath First Search (BFS) algorithm implementation in recursive and non-recursive mode, for graph expansion and path finding.

``````#http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

###CONNECTED COMPONENTS
##NON-RECURSIVE

def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
queue.extend(graph[vertex] - visited)
return visited

###PATH FINDING
##NON-RECURSIVE

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]))

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

###SHORTEST PATH

def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None

shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
``````