Python Breadth First Search optimisation

Question

Given this code...

import Queue

def breadthFirstSearch(graph, start, end):
    q = Queue.Queue()
    path = [start]
    q.put(path)
    while not q.empty():
        path = q.get()
        lastNode = path[len(path) - 1]
        if lastNode == end:
            return path
        for linkNode in graph[lastNode]:
            if linkNode not in path:
                newPath = []
                newPath = path + [linkNode]
                q.put(newPath)

Where graph is a dictionary representing a directed graph, eg, {'stack':['overflow'], 'foo':['bar']} ie, stack is pointing to overflow and foo is pointing to bar.

Can this breadth first search be optimised more? Because I am planning to use it on a very large dictionary.

Answer 1

Why not keep a set of visited nodes so that you don't keep hitting the same nodes? This should work since it doesn't look like you're using a weighted graph. Something like this:

import Queue

def bfs(graph, start, end):
    q = Queue.Queue()
    path = [start]
    q.put(path)
    visited = set([start])

    while not q.empty():
        path = q.get()
        last_node = path[-1]
        if last_node == end:
            return path
        for node in graph[last_node]:
            if node not in visited:
                visited.add(node)
                q.put(path + [node])