Python2. Simple BFS graph traversal. Given a generic graph as a Guido-style adjacency list (dict-of-lists), traverse the nodes, determining if there is a path from start to dest.

graph_bfs.py

##############################################################
#                                                            #
# Copyright 2013 Christopher Abiad. All rights reserved.     #
#                                                            #
##############################################################

__author__ = 'Chris Abiad <cabiad@oanda.com>'

"""
Directed graph
1---->2
| \   |
|   \ |
3     4

- Arrow implies one-way path. No arrow implies bi-directional path.
"""

graph = {
    1: [2, 3],
    2: [4],
    3: [1],
    4: [1, 2],
}

def route_bfs(g, start, dest):
    if start not in g:
        return False
    queue = [start, ]
    visited = {start: True}

    while len(queue) > 0:
        cur = queue.pop(0)
        print 'visiting {0}'.format(cur)
        for item in g[cur]:
            if item == dest:
                print "found dest {0}".format(item)
                return True
            if item not in visited:
                visited[item] = True
                queue.append(item)
    return False

def main():
    print route_bfs(graph, 5, 1)
    print route_bfs(graph, 3, 4)


if __name__ == '__main__':
    main()