[DS] BFS 구현 - python

from collections import deque

def bfs(graph, start_node):
  # visited (set): 중복된 노드를 방문하지 않기 위함
  # traversal (list): 방문 순서를 기록하기 위함
  """
  1. queue가 empty라면 while문 끝
  2. curr = queue.leftpop()
  3. 만약 curr이 visited에 없다면
  4. neighbor이 visited에 없을때만 append
  """
  # 초기 선언
  visited = set()
  traversal = []
  queue = deque([start_node])
  # bfs 시작
  while queue:
    curr = queue.popleft()
    
    if curr not in visited:
      visited.add(curr)
      traversal.append(curr)
      
      for neighbor in graph[curr]:
        if neighbor not in visited:
          queue.append(neighbor)
  
  return traversal
  
graph = {
  'A': ['B', 'C'],
  'B': ['D','E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
}

print(bfs(graph, 'A'))