BFS (breadth first search) graph traversal (Python recipe) by mojave kid

ActiveState Code (http://code.activestate.com/recipes/576675/)

I think you should use collections.deque rather than writing your own queue class. Plus, a search algorithm should not visit nodes more than once.

I think the Pythonic way of implementing visits should be a generator. To give accessing methods enough information to do useful things, every time I visit a node I return its parent. Here is my own implementation of BFS and DFS, with a sample implementation of the shortest_path function.

For a complete Python graph library, I advise you to check NetworkX: http://networkx.lanl.gov/ .

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])

def dfs(g, start):
    stack, enqueued = [(None, start)], set([start])
    while stack:
        parent, n = stack.pop()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        stack.extend([(n, child) for child in new])

def shortest_path(g, start, end):
    parents = {}
    for parent, child in bfs(g, start):
        parents[child] = parent
        if child == end:
            revpath = [end]
            while True:
                parent = parents[child]
                revpath.append(parent)
                if parent == start:
                    break
                child = parent
            return list(reversed(revpath))
    return None # or raise appropriate exception

if __name__ == '__main__':
    # a sample graph
    graph = {'A': ['B', 'C','E'],
             'B': ['A','C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F', 'D'],
             'F': ['C']}

    print(shortest_path(graph, 'A', 'D'))

More compact implementation of the shortest_path function:

def shortest_path(g, start, end):
    paths = {None: []}
    for parent, child in bfs(g, start):
        paths[child] = paths[parent] + [child]
        if child == end:
            return paths[child]
    return None # or raise appropriate exception

To "Matteo Dell'Amico":

"Plus, a search algorithm should not visit nodes more than once"

You are wrong,- algorithm should not visit nodes more than once in one PATH. So it is allowable to visit node several times in different A-D routes. So mojave kid implementation of BFS is correct.

"More compact implementation of the shortest_path function"

I think this is redundant information for breadth first search algorithm, because it strongly depends on goal - what you want to find out from search. If you want to find just shortest route from A to D,- than OK, your suggestions is good. But what if I want to find ALL routes from A to D ? In that case your suggestion is meaningless and mojave kid implementation - is good for such problem. So I suggest, lets leave concrete implementation of BFS algorithm for the script user...

Agnius: http://mathworld.wolfram.com/Breadth-FirstTraversal.html (and all other references I can find) explain clearly that a BFS shouldn't visit nodes more than once. Of course, the shortest_path function does what its name says: it finds the shortest path. Generating all paths is very different, and can easily be computationally prohibitive.

So has this (all shortest paths between 2 nodes) been included in the networkx's functions?

btw, thank you for this implementation. Works just fine.

This doesn't work for a MultiGraph() consisting of 2 different edges between 2 adjacent nodes. What needs to be done then?