[include(틀:이론 컴퓨터 과학)]
[목차]
== 개요 ==
{{{+2 Breadth First Search, BFS}}}

'''너비 우선 탐색'''은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다.
 1. 루트에서 시작한다.
 1. 자식 노드들을 [1]에 저장한다.[* 정확히는 자식의 위치.]
 1. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
 1. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
 1. 위의 과정을 반복한다.
 1. 모든 노드를 방문하면 탐색을 마친다.
아래의 그림을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 '''깊게''' 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 '''넓게''' 탐색하는 것을 볼 수 있다. 

[[파일:external/blog.hackerearth.com/dfsbfs_animation_final.gif]]
깊이 우선 탐색과, 너비 우선 탐색의 차이점을 보여준다. 왼쪽이 깊이 우선 탐색, 오른쪽이 너비 우선 탐색이다.
== 특징 ==
DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.

전 세계의 모든 사람들의 관계를 그래프로 만들고,  'Jack' 과 'Kongnamoo' 의 관계를 잇는 간선을 찾는다고 가정해보자.
BFS를 사용하면 Jack에게 관련된 간선들을 하나씩 파악해나가기 때문에 Kongnamoo를 비교적 빠르게 찾을 수 있지만, DFS로 파악할 경우 Jack의 자식노드를 모두 파악하고 가므로 Jack의 부모님, Jack의 외할머니...Jack의 외할머니의 친구의친구.. 등으로 무한한 길이로 빠져 영원히 종료하지 못하는 것이다. 때문에 DFS에서는 너무 깊게 뻗어나가는 것을 막기 위해 때때로 limit를 걸어두는 것이다.

또한 BFS는 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 '''가중치가 없는 그래프[* 모든 간선에서 주는 가중치가 같다는 뜻이다. 여기에 예시로 나온건 가중치가 안 써있으니 가중치가 없고, 보통 선에 숫자가 쓰여있으면 그게 가중치다.][* 가중치가 있는 그래프에서 최단경로 찾기는 [[다익스트라 알고리즘]] 참고.]에서는'''' 시작점에서 끝점까지의 최단경로를 알아낼 수 있다. 위 움짤의 BFS의 탐색 순서를 살펴볼 때 1번 노드에서 직접 연결된 곳은 2번, 3번, 4번 노드이다. 여기 있는 모든 경로의 길이를 1이라고 한다면, 1번에서 2번, 3번, 4번 노드까지의 길이는 1이다. 똑같은 방법으로 모든 노드 사이의 거리를 구할 수 있다. 따라서 시작점과 끝점이 주어진다면 주어진 그래프(네트위크)에서 최단 경로를 알아낼 수 있다.

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

=== C++ ===
{{{#!syntax cpp
const int MAX = 100'001;

queue<int> q;
bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

void bfs(const vector<int> graph[], int source) { // graph는 인접 리스트, source는 시작 노드
    // source 방문
    q.push(source);
    visited[source] = true;

    while(!q.empty()) { // 큐가 빌 때까지 반복
        // 큐에서 노드를 하나 빼 온다. 이 노드를 current라고 하자.
        int current = q.front();
        q.pop();

        for(int next: graph[current]) { // current의 인접 노드들을 확인한다. 이 각각의 노드를 next라고 하자.
            if(!visited[next]) { // 만일 next에 방문하지 않았다면
                // next 방문
                q.push(next);
                visited[next] = true;
            }
        }
    }
}
}}}

=== Python ===
{{{#!syntax python
def bfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    queue = [start]
    visited[start] = True
    while len(queue) > 0: # 큐가 빌 때까지 반복
        current = queue.pop(0) #queue에서 노드를 하나 빼 온다. 이 노드를 current라고 하자.
        for nxt in graph[current]: # current의 인접 노드들을 확인한다. 이 각각의 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                #nxt 방문
                queue.append(nxt)
                visited[nxt] = True
}}}
파이썬의 pop(0)의 시간 복잡도는 O(N)인데, 시간 복잡도를 우선시한다면 collections 모듈의 deque를 사용하면 된다. 덱이기 때문에 O(1)의 시간 복잡도로 큐를 구현할 수 있다.

== 같이보기 ==
 * [[최선 우선 탐색]]
 * [[깊이 우선 탐색]]

[각주]

[[분류:탐색 알고리즘]]