먼저 버텍스별로 최근접 이웃으로 구성된 리스트를 만듭니다. 이를 인접 리스트(adjacency list)라고 합니다. 파이썬에서는 딕셔너리 자료 구조를 이용해 이를 표현할 수 있습니다.

[in :]

graph = {
  'Amin'  : {'Wasim', 'Nick', 'Mike'},
  'Wasim' : {'Imran', 'Amin'},
  'Imran' : {'Wasim', 'Faras'},
  'Faras' : {'Imran'},
  'Mike'  : {'Amin'},
  'Nick' : {'Amin'}}

BFS 알고리즘은 초기 설정과 메인 루프로 되어 있습니다. 먼저 초기 설정 부분부터 알아봅시다.

초기 설정

그래프 순회는 버텍스들을 한 번씩만 방문해야 합니다. 따라서 방문 기록을 관리하여 앞으로 어떤 버텍스를 방문해야 할지 알아야 합니다. 따라서 다음과 같은 두 자료 구조가 필요합니다.