Breadth first python script

Simple implementation of 'breadth-first search'. This implementation is based on the Common Lisp version in Paul Graham's 'ANSI Common Lisp'.

'm' is a network. We can try to find the shortest path from 'a' to 'd' with:

> shortestPath('a', 'd', m)

----------------------------------------------

m = [['a', 'b', 'c'], ['b', 'c'], ['c', 'd']]

def shortestPath(start, end, network):

    return bfs(end, [[start]], network)

def bfs(end, queue, network):

    if queue == []:

        return 0

    else:

        print queue

        path = queue[0]

        print path

        node = path[0]

        print node

        if node == end:

            return path[::-1]

        else:

            return bfs(end, queue[1:] + newPaths(path, node, network), network)

def newPaths(path, node, network):

    return map(lambda n: [n] + path, assoc(node, network)[1:])

def assoc(key, lst):

    pair = lst[0]

    if key == pair[0]:

        return pair

    else: return assoc(key, lst[1:])