[Algorithm] 그래프 순회 (2) - BFS

그래프의 순회를 BFS를 통해 구현해보고자 한다.

• BFS의 원리 및 개념 설명
  1) BFS는 큐를 이용해서 구현한다.
  2) 넓이 우선 탐색이라는 이름에 맞게 깊이 우선 탐색과 달리 층마다 모든 요소를 훑으면서 내려간다.
• 실제 구현 코드

: 위의 그래프를 BFS 순회하기 위해 아래와 같은 코드를 짜봤다. 이 때, 그래프 객체는 이렇게 구현해두었다.
: FIFO인 큐를 이용하여 맨 앞에서 pop한 요소의 인접 리스트를 탐색중인 배열 끝에 붙이고, 또 탐색하고, 또 pop하고 붙이고의 방법으로 더이상 pop할 요소가 없을 때까지 탐색하도록 했다.

• 인접리스트로 구현을 했기 때문에 BFS도 DFS와 마찬가지로 O(V+E)의 시간복잡도를 가진다.