BFS 란?

BFS는 DFS와 더불어 대표적인 그래프 탐색 방법 중 하나다.
Breadth-first 말 그래도 너비를 우선으로 탐색하는데, 먼저 시작 정점을 방문한 후 인접한 모든 정점을 우선으로 방문하는 방법이다.

해당 정점에 인접한 모든 정점을 방문하면서 방문한 정점에 대해서도 너비 우선 탐색이 이루어져 순차적으로 접근이 가능하다.

/ WIKIMEDIA COMMONS

위 그림은 그래프에서 BFS가 어떤 방식으로 동작하는 지 보여준다.

• 먼저 시작노드인 1을 방문한다.
• 1과 인접한 2, 3, 4를 방문한다.
• 1과 인접했던 정점 중 가장 먼저 방문했던 2와 인접한 5를 방문한다.
• 두번째로 방문했던 3과 인접한 6, 7을 방문한다.
• 마지막으로 방문했던 4와 인접한 8을 방문한다.
  ...

위 과정을 이해했다면 BFS를 구현할 때 queue를 사용한다는 것을 눈치챌 수 있을 것이다.
queue를 활용한 프로세스는 다음과 같다.

1. 시작 노드를 queue에 삽입한다.
2. queue에서 노드를 하나 꺼낸다.
3. 꺼낸 노드의 인접한 모든 노드를 queue에 삽입한다.
4. queue에 노드가 존재하지 않을 때 까지 2, 3을 반복한다.

트리 자료구조에서 BFS로 탐색을 하면 방문했던 정점을 다시 방문할 일이 없어 사이클이 발생하지 않지만, 그래프에선 사이클이 발생할 수 있기 때문에 무한 루프에 빠지는 것을 방지하기 위해 방문 표시를 해야한다.