BFS - Breadth First Search(너비 우선 탐색)

BFS는 트리나 그래프를 방문 또는 탐색하는 방법이다.

아래 움짤을 보면 DFS - (Depth First Search. 깊이 우선 탐색.)는 경로를 설정한 후 한쪽 방향으로 쭉 들어갔다가 나오는(값을 return)하는 형식이지만 BFS는 큐에 값을 넣고 기준점(주로 시작점이다)에서의 거리를 기준으로 순서대로 탐색한다.

특징 : DFS와의 가장 큰 차이로, 여러갈래 중 무한한  길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는경우 DFS탐색은 무한한 길이에서 빠져 나올 수 없지만, BFS는 넓이를 기준으로 모든 경로를 동시탐색하기 때문에 DFS에서 해결하지 못하는 문제를 BFS로 풀 수 있다.

또한 모든 경로를 동시에 탐색하기 때문에 시작점에서 목표지점까지의 최단경로를 알아낼 수 있다.

BFS는 주로 자료구조 <queue>를 사용하여 구현한다.