6.3.1 너비 우선 탐색: 인근 도시부터 여행하기

그림을 먼저 살펴보겠습니다. 그림 6-14는 너비 우선 탐색의 순서를 나타내고 있습니다. L₁은 layer1입니다. 출발 정점 v가 3일 때 너비 우선 탐색은 먼저 정점 3을 방문한 후(L₁) 정점 3에 인접한 모든 정점이 이루는 L₂의 정점을 모두 방문합니다. 다음은 L₂의 정점에서 인접한 정점들이 이루는 L₃의 모든 정점을 방문합니다. 모든 정점을 방문할 때까지 계속 반복합니다.

▲ 그림 6-14 너비 우선 탐색

너비 우선 탐색은 큐를 사용합니다. 이번에는 파이썬이 제공하는 큐를 사용해 볼까요?²