[알고리즘] 그래프탐색: BFS

그래프 탐색이란

• 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법
• Graph: Vertex(어떤 것) + Edge(이어지는 것)
• 그래프 탐색 종류
  • BFS: Breadth-first search (너비 우선 탐색)
    • 자기 자식들을 먼저 탐색
  • DFS: Depth-first search (깊이 우선 탐색)
    • 자식의 자식을 먼저 탐색

Breadth-first search (BFS, 너비 우선 탐색)

---

• 1번에서 부터 시작한다고 생각하면, 자기 자식들을 먼저 탐색함
  • 1 -> 2, 3
• 그 다음 각 자식들에 대한 자식들을 또 탐색함
  • 2 -> 4 / 3 -> 5 (2, 3 끼리 서로 붙어 있는데, 이미 자기들은 탐색 된 애들이라 탐색 x)
• 또 자식들을 탐색
  • 4 -> 5 (pass) / 여기서 3에 대한 자식 5가 이미 탐색 됐기에 패스
• 또 자식들을 탐색
  • 5 -> 6
• 최종적으로 탐색의 순서는 1 - 2 - 3 - 4 - 5 - 6

자료구조

• BFS에 알맞는 자료구조는 Queue임
• Queue는 선입선출의 형태를 띄우고 있는 자료구조임 (아래 그림)

• 그림에서 보면 2가 먼저 들어옴
• 그 다음 4와 5가 순서대로 이어서 들어옴
• 나갈 땐 2가 가장 먼저 들어 왔으니 가장 먼저 나가고, 이어서 4와 5 순으로 이어서 나감
• 따라서 들어올 때 2 - 4 - 5, 나갈 때도 2 - 4 - 5
• 그렇담 위의 BFS 예시에서 확인해보면
  • 1이 먼저 들어옴 (Queue: 1)
  • 1이 자식 2, 3을 데려오면서 1이 나감 (Queue: [1] - 2 - 3)
  • 자식들 2, 3이 각자 자식들 4, 5를 데려오면서 지들은 나감 (Queue: [2] - [3] - 4 - 5)
  • 4는 탐색 할 자식이 없어 데려오는 것 없이 지는 나가고, 5만 6을 데려오면서 나감 (Queue: [4] - [5] - 6)
  • 6도 탐색 할게 없으니 혼자 유유히 나감 (Queue: [6])

아이디어

• 우선 시작점에 연결된 vertex부터 찾기
• 찾은 vertex를 Queue에 저장하기
• Queue의 가장 먼저 것을 뽑아서 반복하기

시간복잡도

• 알고리즘이 얼마나 오래걸리는지에 대한 척도
• 보통 빅오(O)로 표기하면서 가장 최대 얼마나 걸릴 지 추정하는 것임
• BFS: O(V+E) (V: vertex의 수, E: edge의 수)

정리

• 검색할 그래프 정하기
• 방문여부 확인하기 (재방문 금지)
• 대응하는 자료구조 (Queue: BFS 실행)

참고자료

---

• 개발자 장고님의 유튜브 - BFS