breadth_first_search.py

from collections import deque

INF = float('inf')

def bfs(graph, s):
  d = {v: INF for v in graph}
  d[s] = 0
  pi = {s: None}
  queue = deque([s])
  while queue:
    v = queue.popleft()
    for n in graph[v]:
      d_temp = d[v] + 1
      if d[n] > d_temp:
        d[n] = d_temp
        queue.append(n)
        pi[n] = v
  return d, pi


if __name__ == '__main__':
  graph = {'A': ['B', 'C'],
           'B': ['C', 'D'],
           'C': ['B', 'D', 'E'],
           'D': ['E'],
           'E': ['D']}
  print(bfs(graph, 'A'))