메인 루프
다음은 메인 루프를 구현할 차례입니다. 메인 루프는 큐에 있는 버텍스를 하나씩 꺼내어 방문 기록을 확인합니다. 방문 기록이 없다면 해당 버텍스에 연결된 이웃 버텍스를 큐에 추가합니다. 이미 방문한 적이 있다면 큐에 있는 다음 버텍스로 이동합니다.
메인 루프를 파이썬으로 구현해 봅시다.
1. queue에서 첫 번째 버텍스를 꺼내 옵니다.
[in :]
node = queue.pop(0)
2. 해당 버텍스가 visited 리스트에 없다면 이를 visited에 추가합니다. 그리고 이 버텍스의 이웃 버텍스 목록을 그래프에서 불러옵니다.
[in :]
visited.append(node)
neighbours = graph[node]
3. 불러온 이웃들을 queue에 추가합니다.
[in :]
for neighbour in neighbours:
queue.append(neighbour)
4. 메인 루프가 종료되면 그동안 방문한 모든 버텍스가 담긴 visited가 반환됩니다.