DFS

dfs.py

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