Ich habe einen Datensatz, der ein großer ungewichteter zyklischer Graph ist. Die Zyklen treten in Schleifen von ungefähr 5-6 Pfaden auf. Es besteht aus ungefähr 8000 Knoten und jeder Knoten hat 1-6 (normalerweise ungefähr 4-5) Verbindungen. Ich führe Einzelpaar-Kürzeste-Wege-Berechnungen durch und habe den folgenden Code implementiert, um eine Breitensuche durchzuführen.

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

Der obige Code verwendet das Python 2.6 Queue-Modul und getNeighbours () ist einfach eine Subroutine, die einen einzelnen MySQL-Aufruf ausführt und die Nachbarn als Liste von Tupeln zurückgibt, z. (('foo',), ('bar',)). Der SQL-Aufruf ist schnell.

Der Code funktioniert einwandfrei, jedoch dauert das Testen bis zu einer Tiefe von etwa 7 Schichten etwa 20 Sekunden (2,5 GHz Intel 4 GB RAM OS X 10.6).

Über Kommentare zur Verbesserung der Laufzeit dieses Codes würde ich mich freuen.