마지막까지 실행해 봅시다. 그림 6-20을 보면 큐에서 1을 dequeue하여 방문한 후 adj[1]을 가져옵니다. adj[1]={2, 3}인데 정점 2는 이미 방문한 상태이므로 3만 큐에 추가하고 visited[3]을 True로 바꾸어 줍니다.

▲ 그림 6-20 BFS 6

그림 6-21을 보면 큐에서 3을 dequeue하고 방문한 후 adj[3]을 가져오면 adj[3]={1}입니다. 정점 1은 이미 방문했습니다. 이제 큐가 비었군요. 그럼 while 문 실행은 종료되고 BFS 실행도 종료됩니다. 모든 정점을 방문했습니다.

▲ 그림 6-21 BFS 7