BFS

정의

• BFS는 그래프 탐색 알고리즘 중 하나로, 다음과 같은 특징과 절차를 가짐

특징

1. 탐색 방식
   • 루트 노드(시작 노드)에서 시작하여 인접한 모든 노드를 탐색한 후, 다음 레벨의 노드로 이동
   • 탐색 과정에서 “가까운 노드”를 먼저 방문
2. 구현 구조
   • 큐(queue)를 사용하여 탐색을 진행
   • FIFO(First in First out) 원칙에 따라 노드를 탐색함
3. 용도
   • 최단 경로를 구할 때 유용 (가중치가 없는 그래프에서)
   • 연결 요소 확인, 그래프의 모든 정점 택색
4. 시간 복잡도
   • O(V + E), V : 정점의 수, E : 간선의 수
5. 공간 복잡도
   1. 큐와 방문 기록을 저장해야 하므로 O(V)

동작 원리

1. 초기화
   • 시작 노드를 큐에 삽입
   • 방문 기록을 남기기 위해 visited 배열 생성
2. 탐색 반복
   • 큐에서 노드를 하나 꺼냄
   • 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입
   • 방문 기록 업데이트
3. 종료 조건
   • 큐가 빌 때까지 반복

장점

• 최단 경로 탐색에 유리 (가중치가 없는 그래프에서)
• 모든 노드를 동일한 깊이 순으로 탐색