deque

from collections import deque
# def bfs(graph,root):
#   visited = set()
#   queue = deque([root])
  
#   while queue:
#     vertex = queue.popleft()
#     if vertex not in visited:
#       visited.add(vertex)
#       print(vertex)
#       queue.extend(graph[vertex] - visited)
#   return visited

def bfs(graph,root):
  visited = set()
  queue = deque([root])
  
  while queue:
    node = queue.popleft()
    
    if node in visited:
      continue

    visited.add(node)
    print(node)
    queue.extend(graph[node]-visited)

  return visited
  
graph = {
    1: set([2, 3, 8]),  
    2: set([1, 7]),
    3: set([1, 4, 5]),  
    4: set([3, 5]),  
    5: set([3, 4]),  
    6: set([7]),
    7: set([2, 6, 8]),
    8: set([1, 7])
}

bfs(graph,1)