Our FREE site is mostly funded by the Amazon ads ⇓below⇓.

Support us by clicking ⇑above⇑ next time you plan to buy a product on Amazon.

"""
BFS.
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)
"""
G = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def bfs(graph, start):
"""
>>> ''.join(sorted(bfs(G, 'A')))
'ABCDEF'
"""
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
if __name__ == "__main__":
print(bfs(G, "A"))