BFS without queues

breadth_first_search.py

#!/usr/bin/env python

"""
A breadth-first search implementation from:

"MIT Open CourseWare: Introduction to Algorithms"

Lecture 13: Breadth-First Search
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-13-breadth-first-search-bfs/

Erik Demaine

"""

def bfs (graph, src, tgt):
    """Return the shortest path from the source (src) to the target (tgt) in the graph"""

    if not graph.has_key(src):
        raise AttributeError("The source '%s' is not in the graph" % src)
    if not graph.has_key(tgt):
        raise AttributeError("The target '%s' is not in the graph" % tgt)

    level = {src: 0}
    parent = {src: None}

    i = 1
    frontier = [src]
    while frontier:
        next = []
        for u in frontier:
            for v in graph[u]:
                if v not in level:
                    level[v] = i
                    parent[v] = u
                    next.append(v)
        frontier = next
        i += 1

    path = [tgt]
    while parent[tgt] is not None:
        path.insert(0, parent[tgt])
        tgt = parent[tgt]

    return path

    
"""
Test using the graph from: 
https://commons.wikimedia.org/wiki/File:Graph_with_Chordless_and_Chorded_Cycles.svg

"""

test = {
    "a": ["b", "f"],
    "b": ["a", "c", "g"],
    "c": ["b", "d", "g", "l"],
    "d": ["c", "e", "k"],
    "e": ["d", "f"],
    "f": ["a", "e"],
    "g": ["b", "c", "h", "l"],
    "h": ["g", "i"],
    "i": ["h", "j", "k"],
    "j": ["i", "k"],
    "k": ["d", "i", "j", "l"],
    "l": ["c", "g", "k"],
}

assert bfs(test, "a", "e") == ['a', 'f', 'e']
assert bfs(test, "a", "i") == ['a', 'b', 'g', 'h', 'i']
assert bfs(test, "a", "l") == ['a', 'b', 'c', 'l']
assert bfs(test, "b", "k") == ['b', 'c', 'd', 'k']