BFS 개념

 

그래프 탐색 기법 중 하나로 Breadth First Search의 준말로 그대로 번역하면 너비 우선 탐색이라는 뜻이다.

그래프 탐색은 하나의 정점으로부터 시작해서 해당 노드들이 이어진 모든 정점을 한 번씩 탐색하는 것을 말한다.

너비우선 탐색의 경우 깊이(depth)를 탐색하는 것보다 넓게(wide)하게 탐색하는 것을 우선시한다.

그림으로 간단하게 설명하면 위와 같이 노드들이 있을 때 좌우에 있는 노드들을 먼저 탐색하여 A ->​ B ->​ C ->​ D ->​ E ->​ F ->​ G 순으로 탐색하게 된다.

 

BFS의 특징

 

최단경로를 탐색할 때 유용하게 사용하는 방식

큐를 활용하여 큐의 특징인 선입선출(FIFO)로 탐색할 노드의 순서를 저장하고 그 순서대로 탐색

​

위 사진들과 같이 큐에 다음 단게의 노드들이 저장이 되고 큐에 저장된 순서대로 탐색을 하게 된다.