Python Encryption First Search Engine Optimization

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, for example, {'stack':['overflow'], 'foo':['bar']} , i.e. the stack indicates an overflow, and foo indicates a bar.

Is it possible to optimize this search in width more? Because I plan to use it in a very large dictionary.

Answer 1

Why not save the set of visited nodes so that you do not continue to hit the same nodes? This should work, since it doesn't seem like you are using a weighted schedule. Something like that:

 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])