Create a gist now

Instantly share code, notes, and snippets.

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

What would you like to do?
DFS
# Ref. http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
if start in visited:
return
yield start
visited.add(start)
for vertex in graph[start] - visited:
yield from dfs(graph, vertex, visited=visited)
def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for vertex in graph[start] - set(path):
yield from dfs_paths(graph, vertex, goal, path=path + [vertex])
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 dfs(graph, 'A')]))
print(repr([path for path in dfs_paths(graph, 'A', 'F')]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment