너비우선탐색(BFS)는 그래프의 임의의 한 정점에서 출발하여, 연결된 정점들 중 하나에 대해서 너비 순으로 먼저 탐색해 나가는 탐색법이다. 예를 들어 다음과 같은 그래프를 보자.
이를 정점 1을 시작으로 너비우선탐색(BFS)을 했을 경우 여러가지가 가능하지만 가능한 경우의 한 가지는
1 2 4 6 3 5 이다.
따라서 하나의 결과를 위해 다음과 같은 제약조건을 적용한다.
1. 정점 1부터 방문한다.
2. 한 정점에서 갈 수 있는 곳이 여러개 있을 경우 먼저 입력된 정점부터 방문한다.
3. 어떤 정점과 연결되지 않은 경우는 번호가 빠른 순으로 방문한다.
주어진 그래프는 양방향 무가중치 그래프이다.