Можно ли сделать этот поиск в ширину быстрее?
У меня есть набор данных, который представляет собой большой невзвешенный циклический граф. Циклы происходят в циклах примерно 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)
Я бы приветствовал любые комментарии о том, как улучшить время выполнения этого кода.