Можно ли сделать этот поиск в ширину быстрее?

У меня есть набор данных, который представляет собой большой невзвешенный циклический граф. Циклы происходят в циклах примерно 5-6 путей. Он состоит из примерно 8000 узлов, и каждый узел имеет от 1 до 6 (обычно около 4-5) соединений. Я выполняю вычисления по кратчайшему пути в одной паре и реализовал следующий код для поиска в ширину.

from Queue import Queue

q = Queue()
parent = {}
fromNode = 'E1123'
toNode = 'A3455'

# path finding
q.put(fromNode)
parent[fromNode] = 'Root'

while not q.empty():
  # get the next node and add its neighbours to queue
  current = q.get()
  for i in getNeighbours(current):
    # note parent and only continue if not already visited
    if i[0] not in parent:
      parent[i[0]] = current
      q.put(i[0])

  # check if destination
  if current == toNode:
    print 'arrived at', toNode
    break

В приведенном выше коде используется модуль Python 2.6 Queue, а getNeighbours () - это просто подпрограмма, которая выполняет один вызов MySQL и возвращает соседей в виде списка кортежей, например, (( 'Foo'), ( 'бар')). Вызов SQL быстрый.

Код работает нормально, однако тестирование до глубины около 7 уровней занимает около 20 секунд (2,5 ГГц Intel 4GB RAM OS X 10.6)

Я бы приветствовал любые комментарии о том, как улучшить время выполнения этого кода.

Ответы на вопрос(4)

Ваш ответ на вопрос