iframe-proxy | Sunbelt Computer Software

39 lines (31 loc) · 859 Bytes

"""pseudo-code"""

"""

BFS(graph G, start vertex s):

// all nodes initially unexplored

mark s as explored

let Q = queue data structure, initialized with s

while Q is non-empty:

remove the first node of Q, call it v

for each edge(v, w): // for w in graph[v]

if w unexplored:

mark w as explored

add w to Q (at the end)

"""

import collections

def bfs(graph, start):

explored, queue = set(), [start] # collections.deque([start])

explored.add(start)

while queue:

v = queue.pop(0) # queue.popleft()

for w in graph[v]:

if w not in explored:

explored.add(w)

queue.append(w)

return explored

G = {'A': ['B', 'C'],

'B': ['A', 'D', 'E'],

'C': ['A', 'F'],

'D': ['B'],

'E': ['B', 'F'],

'F': ['C', 'E']}

print(bfs(G, 'A'))

Sunbelt Computer Software