Take the 2-minute tour ×

Here http://www.python.org/doc/essays/graphs/ is DFS right ?

I try to do something with 'siblings', but it does not work. Can anyone write BFS similar to code from this site.

share|improve this question
DFS - Depth First Search –  Mark0978 Mar 21 '11 at 15:34
add comment

3 Answers

Yes, it is DFS.

To write a BFS you just need to keep a "todo" queue. You probably also want to turn the function into a generator because often a BFS is deliberately ended before it generates all possible paths. Thus this function can be used to be find_path or find_all_paths.

def paths(graph, start, end):
    todo = [[start, [start]]]
    while 0 < len(todo):
        (node, path) = todo.pop(0)
        for next_node in graph[node]:
            if next_node in path:
            elif next_node == end:
                yield path + [next_node]
                todo.append([next_node, path + [next_node]])

And an example of how to use it:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

for path in paths(graph, 'A', 'D'):
    print path
share|improve this answer
add comment

Why don't you check a decent graph implementation like python-graph?


share|improve this answer
add comment

Here's an O(N * max(vertex degree)) breadth-first search implementation. The bfs function generates nodes in breadth-first order, and for each a generator that can be used to trace a shortest path back to the start point. The lazy nature of the paths means that you can iterate through the generated node to find points you're interested in without paying the cost of building all the intermediate paths.

import collections

GRAPH = {'A': ['B', 'C'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

def build_path(node, previous_map):
    while node:
        yield node
        node = previous_map.get(node)

def bfs(start, graph):
    previous_map = {}
    todo = collections.deque()
    while todo:
        node = todo.popleft()
        yield node, build_path(node, previous)
        for next_node in graph.get(node, []):
            if next_node not in previous_map:
                previous_map[next_node] = node

for node, path in bfs('A', GRAPH):
    print node, list(path)
share|improve this answer
add comment

Your Answer


