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

전체 탐색 방법 중 하나이다.

너비 우선 탐색을 구현하기 위해서는 큐(Queue)를 사용해야 한다.

 

Queue

선입선출(FIFO, First In First Out) 자료구조.

먼저 들어온 데이터가 먼저 나간다. 

Queue Process

 

 

너비 우선 탐색

시작 위치에서부터 차례로 인접한 노드를 탐색하는 방법이다.

너비 우선 탐색 (탐색 시작)

 

너비 우선 탐색 (A 인접 노드, B, C 저장)

 

너비 우선 탐색 (B 인접 노드, D 저장)

 

너비 우선 탐색 (C인접 노드, E, F, G 저장)

 

 

(이하 생략)

이러한 탐색을 계속 반복하여, 모든 노드를 가까운 순서대로 탐색하는 방법이, 너비 우선 탐색이다.