너비우선탐색 BFS

너비우선탐색에 대하여 알아보자!

BFS (Breadth First Search)

Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우

• DFS: 모든 친구 관계를 다 살펴봐야 할지도 모른다.
• BFS: Ash와 가까운 관계부터 탐색

• DFS: 정점부터 한 분기를 깊게 파고 들어 그 분기를 다 탐색한 후 다음 분기를 탐색한다.
• BFS: 정점과 인접한 노드를 기준으로 탐색한다.

BFS의 특징

1. 재귀적으로 동작하지 않는다.
2. Queue를 이용하기 때문에 First In First Out의 원리를 이용한다.
3. 반드시 방문여부를 확인 해주는 검사 장치가 있어야 한다! (자칫하면 무한루프에 빠질 수 있다.)

탐색원리

• 우선 정점의 노드를 Queue에 넣고,
• 이것을 poll() 해주면서
• 이 정점 노드와 연결된 노드들을 Queue에 삽입,
• 그렇다면 위 트리의 탐색 순서는
  1 -> 2 -> 3 -> 4-> 5-> 6-> 7
  

Queue 에는 처음 1이 들어가고 이를 다시 poll()해주면서 인접 노드들인 2, 3을 Queue에 삽입해주며 탐색, 이를 반복하는 것이다.

이러한 BFS의 구현은 앞서 말했다시피 재귀적으로 불가능하다.
구현에 대한 자세한 내용은 아래 문제풀이 링크를 확인해보자!

https://velog.io/@_hennessy_/%ED%8E%98%EC%96%B4%EC%BD%94%EB%94%A9%EC%8A%A4%ED%84%B0%EB%94%94%EA%B2%8C%EC%9E%84%EB%A7%B5-%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC-%EA%B5%AC%ED%95%98%EA%B8%B0