Mitch's Technical Blog

Breadth First Search With Path

July 30, 2018
algorithms, notes, python
permalink

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.

Simple graph

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