Skip to content

Instantly share code, notes, and snippets.

@yasufumy

yasufumy/breadth_first_search.py

Created April 8, 2019 07:05
Show Gist options
  • Save yasufumy/c04e981a40cd5c56911f72e786e3cc73 to your computer and use it in GitHub Desktop.
Save yasufumy/c04e981a40cd5c56911f72e786e3cc73 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment