BFS

BFS(Breadth First Search)는 DFS(Depth First Search)와 반대되는 너비우선탐생방식이다. 꼭대기 기준, 시작점 기준으로 가장 가까운 노드들부터 모두 방문한 후 그 다음 거리의 노드들을 모두 방문하는 탐색 방식이다. 그림 예시가 이해하기 쉬워 캡처해왔다.

BFS 예시

아래와 같은 그림을 생각해보자. 전체 탐색을 할 때 BFS를 이용하면 가장 인접한 노드부터 방문해야한다.
방문할 노드들을 차례로 목록에 push로 저장하고 방문한 노드는 pop으로 제거하며 방문리스트를 작성한다.

1. 시작

A부터 방문하기로 한다.

2. 첫번째 깊이 - A와 거리가 1인 노드

• A를 방문하고 목록에서 제거해준다.
  다음에 방문할 B, C, D를 저장해둔다.
  

3. 두번째 깊이 - A와 거리가 2인 노드들

B, C, D를 방문할 차례다

• 먼저 B를 방문하고 목록에서 제거해준다.
  B 다음 깊이의 노드 E와 F를 목록의 마지막에 저장해준다.
  

• 그 다음은 C를 방문하고 제거.
  C 다음에 방문할 G를 저장해준다.
  

• D를 방문하고 제거.
  D다음 깊이는 없어서 이쪽 라인은 여기서 끝난다.
  

4. 마무리

줄 서 있는 E, F, G를 방문해주면 전체 탐색이 마무리된다.