99클럽 코테 스터디 19일차 TIL BFS

그래프 탐색 기법: BFS

• BFS (Breadth First Search)란?
  
  • 시작 노드부터 인접한 노드를 먼저 완벽하게 탐색하는 그래프 탐색 방법
  • Queue로 구현할 수 있음

그래프

• 그래프 탐색 순서
  
  • 0 -> 1 -> 2 -> 3  -> 4  -> 5  -> 6
• 시간 복잡도
  • 인접 행렬에서의 시간 복잡도: O(V²)
  • 인접 리스트에서의 시간 복잡도: O(V+E)
  • V: 정점(노드)의 개수, E: 간선의 개수

•  

728x90

느낀 점

• 어떤 문제에서 BFS를 사용해야 하는지 파악하는 방법을 알아야겠다.

다음에 학습할 것

• BFS 직접 구현해 보기

반응형

---

BFS에 대해 알아보았다.