Breadth First Search implementation in Python 3 to find path between two given nodes

Question

This is my Breadth First Search implementation in Python 3 that assumes cycles and finds and prints path from start to goal.

Some background - Recently I've been preparing for interviews and am really focussing on writing clear and efficient code, rather than just hacking something up like I used to do.

This is another step in that direction when I'm revisiting some basic algorithms and trying to write best implementations of them as I can from my knowledge and obviously some help and explanations from internet. Any criticism would be helpful. I've tried to make the code as readable and efficient as I could.

from collections import deque
def bfs(graph, start, goal):
 if start == goal:
 print([start])
 return
 queue = deque([start])
 # dict which holds parents, later helpful to retreive path.
 # Also useful to keep track of visited node
 parent = {}
 parent[start] = start
 while queue:
 currNode = queue.popleft()
 for neighbor in graph[currNode]:
 # goal found
 if neighbor == goal:
 parent[neighbor] = currNode
 print_path(parent, neighbor, start)
 return
 # check if neighbor already seen
 if neighbor not in parent:
 parent[neighbor] = currNode
 queue.append(neighbor)
 print("No path found.")
def print_path(parent, goal, start):
 path = [goal]
 # trace the path back till we reach start
 while goal != start:
 goal = parent[goal]
 path.insert(0, goal)
 print(path)
if __name__ == '__main__':
 graph = {'A': set(['B', 'C']),
 'B': set(['A', 'D', 'E']),
 'C': set(['A', 'F']),
 'D': set(['B']),
 'E': set(['B', 'F']),
 'F': set(['C', 'E'])}
 bfs(graph, 'D', 'F')

Answer 1

Comments

Provide a docstring, detailing what the code does and returns

Pep-8

When writing Python, it is advised to follow the styleguide. This means snake_case instead of hybridCamelCase for variable.

Another formatting I use is

graph = {
 'A': set(['B', 'C']), 
 'B': set(['A', 'D', 'E']),
.... 
 'F': set(['C', 'E']),
}

Instead of your representation. If ever you change something to this, the diff of your code versioning system will be a lot clearer and simpler. (note the trailing comma after the last entry)

Separate presentation with the calculation.

Use a function traversing the graph, and returning the path, and another one to present the result (if needed). This way, you can also write unittests that don't need to mock print to test the algorithm

Use an exception to signal something exceptional

Instead of just printing that there is no path, you can signal this by returning None or raising an exception

class NoPathException(Exception): pass

Data structure

instead of keeping a separate dict with the path, it is easiest if you stack the queue with the node and the path used to reach it so far. That make your effort a lot easier. There is no need to keep the dict, but an ordinary set with the nodes visited should suffice.

Minimize the indents

To minimize the number of indents and keep your line length under control, instead of

for item in loop:
 if condition:
 do_something()

you can do:

for item in loop:
 if not condition:
 continue
 do_something()

Especially with a lot of nested conditions, this is a lot more compact.

Complete algorithm

def bfs2(graph, start, goal):
 """
 finds a shortest path in undirected `graph` between `start` and `goal`. 
 If no path is found, returns `None`
 """
 if start == goal:
 return [start]
 visited = {start}
 queue = deque([(start, [])])
 while queue:
 current, path = queue.popleft()
 visited.add(current)
 for neighbor in graph[current]:
 if neighbor == goal:
 return path + [current, neighbor]
 if neighbor in visited:
 continue
 queue.append((neighbor, path + [current]))
 visited.add(neighbor) 
 return None # no path found. not strictly needed
if __name__ == '__main__':
 graph = {
 'A': set(['B', 'C']), 
 'B': set(['A', 'D', 'E']),
 'C': set(['A', 'F']), 
 'D': set(['B']), 
 'E': set(['B', 'F']), 
 'F': set(['C', 'E']),
 }
 path = bfs2(graph, 'D', 'F')
 if path:
 print(path)
 else:
 print('no path found')

Answer 2

• It seems more logical to test the currNode against goal, rather than its neighbours:

  while queue:
   currNode = queue.popLeft()
   if currNode == goal:
   print_path(....)
   return
   for neighbor in graph[currNode]:
   ....
  

  Notice that such approach eliminates the need of a special casing if start == goal:.

• Printing the path (or No path found message) from inside of bfs violates the single responsibility principle. It is better to return something (a path or None), and let the caller decide what to do.

• parent[start] = start feels icky. start is not its own parent, at least as in the context of the path. Also notice that the loop of print_path doesn't care who is the start's parent, so this assignment has no purpose anyway.

• jatinw21: - First point makes total sense logically but wouldn't it decrease efficiency as we would have to expand all neighbours in worst case before finding the goal, as opposed to directly returning when we first see them? - For third, the parent dict also acts as visited set. If I remove parent line for start, another node can come back traversing to it as it is not seen. Maybe best way is to add parent[start] = None?