Skip to content

Instantly share code, notes, and snippets.

@dpapathanasiou
Created April 2, 2019 23:13
  • Star 5 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save dpapathanasiou/748a14e56c9171671121710d1905c94f to your computer and use it in GitHub Desktop.
Breadth-First Search in Python
#!/usr/bin/env python
"""
A breadth-first search implementation from:
"Python Algorithms: Mastering Basic Algorithms in the Python Language"
by Magnus Lie Hetland
ISBN: 9781484200551
Input consists of a simple graph of { node: [list of neighbors] } plus a source and target node.
"""
from collections import deque
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)
parents = {src: None}
queue = deque([src])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in parents:
parents[neighbor] = node
queue.append(neighbor)
if node == tgt:
break
path = [tgt]
while parents[tgt] is not None:
path.insert(0, parents[tgt])
tgt = parents[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']
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment