 JGuizard
5/1/2016 - 9:26 AM

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

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

``````###GRAPH EXPANSION
##NON RECURSIVE

def dfs(graph, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}

##RECURSIVE

def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited

dfs(graph, 'C') # {'E', 'D', 'F', 'A', 'C', 'B'}

###PATH FINDING
##NON-RECURSIVE

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

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

##RECURSIVE

def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for next in graph[start] - set(path):
yield from dfs_paths(graph, next, goal, path + [next])

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