BFS

---

BFS는 컴퓨터 알고리즘 분야에서 2가지 알고리즘의 약자이다.

• Breadth First Search(너비 우선 탐색)

반대 개념은 DFS이다.

• Best First Search(최선 우선 탐색)

1 너비 우선 탐색

너비 우선 탐색은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다.

1. 루트에서 시작한다.
2. 자식 노드들을 [1]에 저장한다.
3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5. 위의 과정을 반복한다.
6. 모든 노드를 방문하면 탐색을 마친다.

아래의 움짤을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다. 사실 내가 썼지만 나도 무슨 말인지 모르겠다

깊이 우선 탐색과, 너비 우선 탐색의 차이점을 보여준다. 왼쪽이 깊이 우선 탐색, 오른쪽이 너비 우선 탐색이다.

1.1 특징

DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.

또한 BFS는 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 시작점에서 끝점까지의 최단경로를 알아낼 수 있다. 위 움짤의 BFS의 탐색 순서를 살펴볼 때 1번 노드에서 직접 연결된 곳은 2번, 3번, 4번 노드이다. 여기 있는 모든 경로의 길이를 1이라고 한다면, 1번에서 2번, 3번, 4번 노드까지의 길이는 1이다. 똑같은 방법으로 모든 노드 사이의 거리를 구할 수 있다. 따라서 시작점과 끝점이 주어진다면 주어진 그래프(네트위크)에서 최단 경로를 알아낼 수 있다.

1.2 소스 코드로의 구현

BFS는 재귀 호출(Recursion Call)을 이용하여 소스 코드로 구현하는 DFS와는 달리, 자료 구조 Queue를 사용하는 경우가 일반적이다. 배열에서 사용하는 경우, 방향 데이터를 이용해 배열의 시작점에서 범위를 넖혀 가면서 탐색하는 것이다.

2 최선 우선 탐색

매 탐색마다 휴리스틱 값을 찾아서 가장 최선의 휴리스틱 값의 노드를 확장한다.