Performance of BFS in Python 3

1. Review

1. The bfs function relies on a global variable distance. This make it hard to test (you have to remember to set up the distance list before you call bfs) and means that it can't be used from multiple threads. It would be better if bfs constructed all its own data structures.

2. The path variable is a tuple of all the vertices that have been visited so far. Adding a new element to the path, as in path = path + (u,), requires copying out the old path. This makes the overall runtime \$\Omega(n^2)\$. But path is not actually used for anything, so you could just remove it.

3. queue.Queue is a thread-safe data structure intended for use by multi-threaded programs. It has to take and release a lock for every operation, so it is overkill to use this in a single-threaded program. It is more than ten times faster to use collections.deque instead.

4. The code handles the exceptional situation (no path is found) by returning an exceptional value (−1). This is an error-prone design because it would be very easy for the caller to forget to check for the exceptional value. It would be easy to write code like this:

   dist = bfs(graph, start, end)
   if dist <= goal:
       print("reachable in {} steps or fewer".format(goal))
   

   which would go wrong when dist is -1. It's better to handle an exceptional situation by raising an exception.

5. The code checks to see whether a vertex is equal to end after removing it from the queue. But it would be better to do this check before adding a vertex to the queue — that way you wouldn't have to wait for the vertex to move all the way up the queue before you spot that the search is done.

   This optimization works for this problem because all the edges have the same length and so breadth-first search adds vertices to the queue in order by their distance from the start. This means that as soon as you've found a path to end you know that more searching cannot find a shorter path.

6. The value distance[u] + 1 is computed again for every child. It would be better to compute it once and remember it.

2. Revised code

from collections import deque

class NotFound(Exception):
    """Exception raised when no path is found."""

def bfs(graph, start, end):
    """Return the shortest distance from start to end in graph, which is
    represented as a mapping from a vertex to a list of adjacent
    vertices. If there is no path from start to end, raise NotFound.
    """
    # Mapping from v to shortest distance from start to v.
    distance = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        d = distance[u] + 1
        for neighbour in graph[u]:
            if neighbour not in distance:
                if neighbour == end:
                    return d
                distance[neighbour] = d
                queue.append(neighbour)
    else:
        raise NotFound()