너비 우선 탐색은 각 정점 v에 다음과 같은 두 개의 값을 할당합니다:
  • 거리. 소스 정점에서 정점 v에 이르는 아무 경로에 있는 변의 최소 수를 나타냅니다.
  • 선행 정점. 소스 정점에서 가장 짧은 경로 내 v의 선행자 정점. 소스 정점의 선행자는 null과 같은 특수 값을 가지는데 이는 선행 정점이 없음을 의미합니다.
소스 정점에서 정점 v에 이르는 경로가 없다면 v의 거리는 무한하며 그 선행 정점은 소스의 선행 정점과 같이 특별한 값을 갖게 됩니다.
예를 들어 0부터 7까지의 여덟 개 정점을 갖는 무방향 그래프를 생각해봅시다. 여기서 정점의 숫자는 정점의 위나 아래에 나타냈습니다. 각 정점의 내부에는 두 개의 숫자가 적혀 있습니다: 정점 3인 소스와의 거리와 정점 3에서의 최단 경로에 있는 선행자의 숫자입니다. -는 null을 의미합니다.
BFS 결과
BFS에서는 시작할 때 각 정점의 거리와 선행 정점을 특별한 값(null) 으로 초기화합니다. 소스 정점에서 시작해 이 정점의 거리에 0을 할당합니다. 그런 후 소스 정점의 이웃을 모두 방문하여 각 이웃의 거리를 1로 설정하고 선행 정점에 소스 정점의 값을 대입합니다. 그런 후 소스 정점과의 거리가 1인 정점의 이전에 방문된 적이 없는 모든 이웃을 방문합니다. 방문된 모든 정점의 거리를 2로 설정하고 선행 정점에는 방문한 정점의 숫자를 설정합니다. 계속해서 소스 정점에서 다다를 수 있는 모든 정점을 방문할 때까지 이 과정을 게속합니다. 이 때 거리가 k, plus, 1인 정점을 방문하기 전에 소스에서 거리가 k인 모든 정점을 항상 방문해야 합니다.
아래는 위 예제의 각 단계와 각 단계를 실현하기 위한 과정을 설명한 것입니다.
  • 소스 정점 3부터 시작시작합니다. 정점 3의 거리를 0으로 설정합니다.
  • 그런 후 정점 2와 6으로 가서 거리를 1로, 선행 정점을 정점 3으로 설정합니다.
  • 소스에서 거리가 1인 정점들로 갑니다. 정점 2부터 시작해 봅시다. 정점 2에서 정점 4와 5를 방문하여 이들의 거리를 2로, 선행 정점을 정점 2로 설정합니다. 정점 3은 이미 방문했으므로 가지않습니다.
  • 정점 6에서는 방금 정점 2에서 방문한 정점 3과 정점 5는 방문하지 않습니다.
  • 이제 소스에서 거리가 2인 정점들을 가보도록 하죠. 정점 4를 먼저 가도록 합시다. 정점 2는 이미 방문되었습니다. 정점 1로 가서 거리를 3으로, 선행 정점을 정점 4로 설정합니다.
  • 정점 5에서는 이웃하는 모든 정점에 한 번씩 갔으니 아무데도 가지 않습니다.
  • 이제 소스에서 거리가 3인 정점들을 가보도록 합시다. 그런 정점은 정점 1뿐입니다. 그 이웃 정점인 정점 4와 5는 이미 방문하였습니다. 그렇지만 정점 0은 아닙니다. 정점 0으로 가서 거리를 4로, 선행 정점을 정점 1로 설정합니다.
  • 이제 소스에서 거리 4인 정점들을 갑니다. 그런 정점은 정점 0과 그 이웃 정점인 1뿐인데 이미 방문했으니 끝입니다!
정점 3에서 정점 7로 가는 경로가 없기 때문에 검색 과정에서 정점 7은 한 번도 가지 않았다는 것을 기억하십시오. 이 정점의 거리와 선행 정점은 초기값인 null인 채로 남아 있습니다.
몇 가지 의문점이 생깁니다. 한 가지는 어떤 정점에 이미 가봤는지 여부를 어떻게 결정하는지 하는 것입니다. 이건 쉽습니다. 한 번 가보기 전까지는 정점의 거리가 null일 것이고 가보게 되면 거리에 따라 값이 주어질겁니다. 그렇기 때문에 어떤 정점의 이웃 정점을 검사할 때 그 거리가 현재 null로 되어 있는 정점만 가면 됩니다.
또 다른 의문점은, 어떤 정점을 이미 가봤지만 그 곳에서 출발한 적은 없는지 어떻게 확인하는가 하는 문제입니다. 여기서 를 사용하게 됩니다. 이는 항목을 삽입하고 제거할 수 있는 데이터 구조인데 여기서 제거되는 항목은 항상 그 큐에 가장 오래 있었던 항목입니다. 이렇게 작동하는 것을 선입선출(first in, first out)이라고 부릅니다. 큐에서는 3가지 연산을 할 수 있습니다.
  • enqueue(obj)은 큐에 객체를 삽입합니다.
  • dequeue()는 가장 오래 큐에 있었던 객체를 큐에서 제거하고 이 객체를 반환합니다.
  • isEmpty()는 현재 큐에 객체가 없으면 을 반환하고 큐에 하나 이상의 객체가 있으면 거짓을 반환합니다.
어떤 정점을 처음 가게 되면 그 정점을 enqueue합니다. 소스 정점은 항상 제일 먼저 가는 정점이므로 시작할 때 소스 정점을 큐에 enqueue합니다. 어느 정점을 다음으로 가야 할지 결정하기 위해 큐에 가장 오래 있었던 정점을 선택하여 이를 큐에서 제거합니다. 즉, dequeue()에서 돌려주는 정점을 이용하는 것입니다. 예제 그래프에서 적용해보면 각 단계에서 큐는 다음과 같습니다. 큐 상태와 함께 이전의 설명도 함께 나타냈습니다.
  • 처음에 큐는 거리 0인 정점 3만 포함합니다.
  • 정점 3을 큐에서 제거하고 정점 2와 6을 큐에 삽입합니다. 둘 모두 거리가 1입니다. 이제 큐는 거리 1인 정점 2와 거리 1인 정점 6이 들어있습니다.
  • 정점 2를 큐에서 제거하고 거리가 2인 정점 4와 5를 큐에 삽입합니다. 큐는 이제 거리 1인 정점 6, 거리 2인 정점 4, 거리 2인 정점 5가 들어있습니다.
  • 정점 6을 큐에서 제거하고 어떤 정점도 큐에 삽입하지 않습니다. 큐에는 이제 거리 2인 정점 4와 거리 2인 정점 5가 있습니다.
  • 정점 4를 큐에서 제거하고 거리 3인 정점 1을 큐에 삽입합니다. 큐에는 이제 거리 2인 정점 5와 거리 3인 정점 1이 있습니다.
  • 정점 5를 큐에서 제거하고 어떤 정점도 큐에 삽입하지 않습니다. 이제 큐에는 거리 3인 정점 1만이 있습니다.
  • 정점 1을 큐에서 제거하고 거리 4인 정점 0을 큐에 삽입합니다. 큐에는 이제 거리 4인 정점 0만이 있습니다.
  • 정점 0을 큐에서 제거하고 어떤 정점도 큐에 삽입하지 않습니다. 큐는 이제 비어 있습니다. 큐가 비어있으니 너비 우선 탐색을 끝냅니다.
각 순간에 큐는 같은 거리를 가진 모든 정점을 포함하고 있거나 아니면 거리 k의 정점 다음에 거리 k, plus, 1의 정점을 포함하고 있다는 것을 주목하십시오. 이게 바로 k, plus, 1의 정점으로 가기 전에, k의 모든 정점을 가는것을 보장하는 방법입니다.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.