# Breadth First Search With Path

This implementation of breadth first search (BFS) is based roughly on pp. 107-110 of *grokking algorithms*, with one enhancement: it not only finds the shortest path, it shows it.

None of the edges or vertices have weight, each node has a single character name, and the path is represented as a simple string of nodes. In other words, this is for demonstration and learning, not production.

This might be a simplified special case of Dijkstra's algorithm (i.e. no edge weights), but I won't know until I get better acquainted with Dijkstra.

Here's a visual representation of the graph that's modeled in the script.

from collections import deque graph = {'A': ['E', 'B', '3', '1'], '1': ['2', 'A'], '2': ['1'], '3': ['A'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['C'], 'E': ['A', 'F'], 'F': ['E', 'G'], 'G': ['F', 'D']} def find_path(start, dest): """ >>> find_path('A', 'D') 'ABCD' >>> find_path('3', 'A') '3A' >>> find_path('D', '2') 'DCBA12' >>> find_path('Z', 'A') 'Start not in graph' >>> find_path('A', 'Z') 'Dest not in graph' >>> find_path('A', 'A') 'A' """ if not graph.get(start): return 'Start not in graph' if not graph.get(dest): return 'Dest not in graph' # Initialize visited = [] search_queue = deque() search_queue += start while search_queue: next_node_with_path = search_queue.popleft() # the search_queue is implemented to contain prior state (i.e. path) # so we must extract the actual node from the end next_node = next_node_with_path[-1] if next_node == dest: return next_node_with_path else: visited.append(next_node) add_neighbors(next_node_with_path, search_queue, visited) return 'Not found' def add_neighbors(node_with_path, search_queue, visited): ''' node_with_path should contain the new node along with its prior path ''' node = node_with_path[-1] for n in graph.get(node, []): if not n in visited: # We want to store the prior path too search_queue.append(node_with_path + n) if __name__ == '__main__': from doctest import testmod testmod(verbose=True)

Contact: hello at escapefromsql.net